2020-10-14

AtCoder ARC 105 E - Keep Graph Disconnected (橙色, 700 点)

AtCoder AtCoder700点橙色diff ARC-E ゲームパリティ場合分け連結成分グラフ Union-Find DP 対称戦略思わず解きたくなる興味深い良問マルチテストケース問題操作操作:挿入数学的帰納法に基づく考察グラフ上のゲーム

とてもシンプルな設定で面白かった！でもバグらせてそうで、提出するのは怖かった。

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 $N$ は非連結である。

先手と後手が、交互に 1 本ずつ辺を追加していく。ただし

多重辺や自己ループを作ってはいけない
頂点 1 と頂点 $N$ とが連結になってはいけない

先に操作を行えなくなった方が負けである。双方最善尽くしたときにどちらが勝つか？(というテストケースが $T$ 個与えられる)

制約

$N$ の総和は $2 \times 10^{5}$ 以下
$M$ の総和は $2 \times 10^{5}$ 以下

考えたこと

めちゃくちゃシンプルな設定で面白そう！！これ最終結果は「2 つの分断された完全グラフ」という状態になるわけだ！そして、双方がいかに上手に連結成分をマージしていくかが戦略の鍵となる。

最終状態に応じて、「追加できる本数」の偶奇が変わる。追加できる本数が奇数本なら先手勝ち、偶数本ならば後手勝ちとなる。

まずは、連結成分のサイズによって完全グラフにしたときの辺の本数がどのようになるかを調べる。頂点数を $V$ としたとき、

$V ≡ 0, 1 \pmod 4$ のとき、 $f(V) = \frac{1}{2}V(V-1)$ は偶数
$V = 2, 3 \pmod 4$ のとき、 $f(V) = \frac{1}{2}V(V-1)$ は奇数

となっていることがわかる (頂点数 $V$ の完全グラフの辺数を $f(V)$ とする)。

N に応じてどうなるか

次に、 $N \pmod 4$ によって、ゲーム性がどのようになるのかを分析する。最終結果の連結成分のサイズを $S, T$ ( $S + T = N$ ) とする。そうすると

$N ≡ 1 \pmod 4$ のときは、 $S \pmod 4$ がいずれであっても $f(S) + f(T)$ は偶数
$N ≡ 3 \pmod 4$ のときは、 $S \pmod 4$ がいずれであっても $f(S) + f(T)$ は奇数

ということがわかった。つまり、 $N$ が奇数のときは、いかなる戦略をとろうとも、どちらが勝つかの運命があらかじめ決まっていることがわかった。残りの $N$ に対しては、次のようになった。

のとき
- $S$ が偶数のとき、 $f(S) + f(T)$ は偶数
- $S$ が奇数のとき、 $f(S) + f(T)$ は奇数
のとき
- $S$ が偶数のとき、 $f(S) + f(T)$ は奇数
- $S$ が奇数のとき、 $f(S) + f(T)$ は偶数

つまり、 $N$ が偶数のときは、色々な場合が考えられるものの、基本的には

先手としては、偶数サイズの連結成分を作りたい (後手は阻止したい)
先手としては、奇数サイズの連結成分を作りたい (後手は阻止したい)

のいずれかの状況になる、と言えることがわかった。このうちのどちらの状況に該当するのかは簡単に特定できる。

先手が偶数サイズの連結成分を作りたいとき

初期状態で、頂点 1 を含む連結成分 (S とする) のサイズを s、頂点 N を含む連結成分 (T とする) のサイズを t とする。このとき

s と t がともに奇数のとき、先手がほかの奇数サイズの連結成分を S または T にマージした場合、後手はさらに別の奇数サイズの連結成分 (その存在は保証できる) をマージすることで「s と t がともに奇数」という状況をキープできる、よって後手必勝
s と t のいずれかが偶数のとき、先手は真っ先に「s と t がともに偶数」という状況を作ることができる。その後は後手が何をしてきてもかならず「s と t がともに偶数」という状態をキープできる、よって先手必勝

先手が奇数サイズの連結成分を作りたいとき

同様に議論で次のように言える。

s と t がともに偶数のとき、後手は「s と t がともに偶数」という状態をキープするように働きかけられるので、後手必勝
s と t のどちらかが奇数のとき、先手は真っ先に「s と t がともに奇数」という状態を作ることができて、その状態をキープできるので、先手必勝

コード

以上をまとめると、 $O(N + M)$ で判定できる。下のコードでは Union-Find を使っているので、 $O(N + M\alpha(N))$ となる。

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

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

bool solve() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        uf.merge(u, v);
    }
    int s = uf.size(0) % 2, t = uf.size(N-1) % 2;

    // N が奇数のときは運命が最初から決まっている
    if (N % 2 == 1) {
        long long sum = (N-1) * (N-2) / 2;
        if ((sum - M) % 2 == 0) return false;
        else return true;
    }

    // 偶数サイズの連結成分を作りたいとき
    if ((N * (N - 1) / 2 - M) % 2 == 1) {
        if (s == 1 && t == 1) return false;
        else return true;
    }
    // 奇数サイズの連結成分を作りたいとき
    else {
        if (s == 0 && t == 0) return false;
        else return true;
    }
}


int main() {
    int T;
    cin >> T;
    while (T--) {
        if (solve()) cout << "First" << endl;
        else cout << "Second" << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます