🍣

ABC296 E - Transition Game

2023/04/02に公開

問題概要

長さ $N$ の整数列 $A=(A_1,A_2\dots,A_N)$ が与えられる。ここで、各 $i$ について $1\leq A_i \leq N$ が保証される。
高橋君,青木君は、 $N$ 回のゲームを行う。 $i=1,2,\dots,N$ 回目のゲームの内容は、以下の通り:

青木君は、正整数 $K$ を指定する。

高橋君は、青木君の選んだ $K$ を聞いたうえで、 $1$ 以上 $N$ 以下の正整数 $s$ を選び、ひとつ黒板に書く。

その後、以下の操作を $K$ 回繰り返す:
黒板に書かれている数を $x$ としたとき、黒板に書かれていた整数を消し、新たに $A_x$ を書き込む。

$K$ 回の操作を終えた後、書かれていた回数が $i$ であれば高橋君の勝利,そうでなければ青木君の勝利

なお、毎ゲーム開始時,黒板には何も書かれていない。

両者が自身が勝つために最適に行動したとき、高橋君は最大何回のゲームで勝利することができますか?

$1\leq N\leq 2\times10^5$
$1\leq A_i\leq N$

解法

言い換え

ゲームの内容が分かりづらい...というか、両者にとって「最適な行動」が分からない。
いろいろ観察してみよう...
特徴的なのは、 $x\leftarrow A_x$ という置き換えである。これをうまく活用したい...

動きをわかりやすくするために、 $v\to A_v$ に辺を張った有向グラフを作る。このグラフを $G$ とする。 $G$ は次の性質を持っている。

各頂点の出次数はちょうど $1$
「黒板に $x$ が書かれた状態から初めて、 $k$ 回の操作を行った後に書かれている数」
は、
「 $G$ において $x$ から $k$ 進んだ頂点の番号」
と同じ。

これを使うと、高橋君は次の戦略をとればよい:

$i$ から $K$ 回さかのぼった頂点が存在すればそれを $s$ に指定する

例

例えば $N=5,A=(2,3,4,2,1)$ とかだとグラフは次のような感じ。

例えば、 $i=2$ 回目のゲームで $K=2$ を指定されたなら、頂点 $2$ から $2$ 遡った頂点である $5$ を選べばよい。
他にも、 $i=3,K=2$ のときは $1$ でもいいし、 $4$ でもいい。
一方、そのような頂点が存在しないこともある。例えば、 $i=5,K=2$ など...このようなときはそもそもどうやっても勝てないことが観察できる

観察

グラフを観察してみると、次のような性質が分かる。

基本的には $K$ をめちゃくちゃでかくとられると、 $K$ ステップ遡ることはできない。

例

例えば $N=5,A=(2,3,4,2,1)$ の時を考える

この時、 $i=1,K=10^{100}$ とかを指定されると $K$ 回遡ることはできない

ただ、これを回避できる状況が存在する!!!
それは、 $G$ に $i$ を含む有向サイクルが存在するとき。
逆にそうじゃないときは、上の戦略により遡れなくすることが可能となってしまう...

結論

ということで、 $i$ 回目のゲームで勝つための条件は $G$ に $i$ を含む有向サイクルが存在することです。
したがって、 $G$ の有向サイクルを列挙することで解けます。

実装

与えられるグラフは Functional Graphなので、SCC(強連結成分分解)を使うと楽に実装できる。
具体的には、

SCCする
各成分を見る。次のいずれかを満たしていれば、その成分のサイズを答えに加算する
- サイズが $1$ で、かつ自分から自分への辺がある
- サイズが $2$ 以上

#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>

int main(){
    int n;
    cin >> n;
    atcoder::scc_graph g(n);
    vector<int> to(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;
        to[i] = a;
        g.add_edge(i, a);
    }
    auto res = g.scc();
    int ans = 0;
    for (auto& vec : res) {
        if (vec.size() >= 2){
            ans += vec.size();
        }else{
            int v = vec.front();
            if (to[v] == v) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

AC:101ms

問題概要

解法

言い換え

観察

結論

実装

Discussion