AOJ 2376 DisconnectedGame (JAG 冬合宿 2010 day3-H) (600 点)

こないだの ARC でめっちゃ似た問題が出たので！これは、SolveMe を含む、りんごさんによる伝説のセット。

drken1215.hatenablog.com

• 問題へのリンク

問題概要

頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。このグラフ上で 2 人で次のようなゲームを行う。

• グラフの隣接していない頂点間を辺で結ぶ
• ただし、グラフ全体が連結になるようにしてはならない

先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

• 

考えたこと

最終状態は として、頂点数 の完全グラフと頂点数 の完全グラフが形成された状態で終了する。

よって、最終的な辺の本数は となるので、初期状態のグラフの辺数を として、追加される本数は となる ( とおく)。

• が奇数のとき、先手の勝ち
• が偶数のとき、後手の勝ち

といえる。よって、先手としては が奇数となるように動き、後手としては が偶数となるように動く。ここでこの記事での議論を。

drken1215.hatenablog.com

• が奇数のとき、 が偶数であっても奇数であっても の偶奇は一意 (よって戦略性はなく最初から運命は決まっている)
• が偶数のとき、先手にとって (偶数, 偶数) にしたいか、(奇数, 奇数) にしたいかはあらかじめ特定できる

というふうになっている。ここから先は DP でも殴れそうだけど、ちょっと考察してみた。

まず大前提として、最終状態が (奇数, 奇数) で終わるケースはかなり少ない。なぜなら、先手と後手のうちのどちらかは (偶数, 偶数) で終わることを目指しているため、(奇数) と (奇数) をマージしまくって (奇数) を消すことを目論むからだ。

また、

• (奇数) と (奇数) をマージする瞬間、「新たに追加可能な辺」は、マージ辺含めて奇数本増えることに注意。つまり、「マージ」という行為をしたくない局面の場合、(奇数) と (奇数) を 1 回マージすることによって、「マージ」という行為をどちらが先に打たなければならないかを入れ替えることができる

• (偶数) を含む 2 つの連結成分をマージする瞬間は、「新たに追加可能な辺」は、マージ辺含めて偶数本増えるので、「マージ」手待ちの先手後手の状況に変わりはない

先手が (偶数, 偶数) を目指しているとき

とりあえず一瞬でも (偶数) が存在する状態で手番が回ってきたら、それ以降 (偶数) が常に 2 個以上ある状態をキープできるので勝てる。

初期状態が

• (奇数, 奇数) のとき
• (奇数, 奇数, 奇数, 奇数) であって、マージなしで打てる手が偶数本であるとき
  • 先手が先に (奇数) と (奇数) をマージせざるを得なくなり、後手がすかさず (奇数, 奇数) の状態を作るので負ける

については、後手必勝となる。初期状態が (偶数) を含むときは明らかに先手勝ちである。

一方、初期状態が (奇数) のみであっても上記の場合以外は先手が勝てる。とにかく一度でも後手を「(奇数) と (奇数) のマージをせざるを得ない状態」に追い込めばよい。(奇数) が 6 個以上あれば、仮にマージなしで打てる手が偶数本しかなかったとしても、一度 (奇数) と (奇数) でマージしておくことで、相手をその状態に追い込むことができる。

先手が (奇数, 奇数) を目指しているとき

とにかく (偶数) が存在する状態で相手に手番を渡したら終わりなのでシビアである。先ほどと同様の議論により、初期状態が

• (奇数, 奇数) のとき
• (奇数, 奇数, 偶数) のとき
• (奇数, 奇数, 奇数, 奇数) であって、マージなしで打てる手が奇数本であるとき
• (奇数, 奇数, 奇数, 奇数, 偶数) であって、マージなしで打てる手が奇数本であるとき

だけは先手が勝てる。それ以外は負ける。

コード

結構場合わけがエグいので、やっぱり DP で殴った方がよいかもしれない。

#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() {
    long long V, E = 0;
    cin >> V;
    UnionFind uf(V);
    for (int i = 0; i < V; ++i) {
        string str;
        cin >> str;
        for (int j = i+1; j < str.size(); ++j) {
            if (str[j] == 'Y') {
                ++E;
                uf.merge(i, j);
            }
        }
    }
    long long num = 0;
    map<int,long long> ma;
    for (int i = 0; i < V; ++i) ma[uf.root(i)]++;
    int odd = 0, even = 0;
    for (auto it : ma) {
        long long n = it.second;
        if (n & 1) ++odd;
        else ++even;
        num += n * (n-1) / 2;
    }
    long long rem = (num - E) % 2;

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

    // (偶数, 偶数) にしたいとき
    if ((V * (V-1) / 2 - E) % 2 == 1) {
        if (even == 0 && odd == 2) return false;
        else if (even == 0 && odd == 4 && rem == 0) return false;
        else return true;
    }
    // (奇数, 奇数) にしたいとき
    else {
        if (even <= 1 && odd == 2) return true;
        else if (even <= 1 && odd == 4 && rem == 1) return true;
        else return false;
    }
}

int main() {
    if (solve()) cout << "Taro" << endl;
    else cout << "Hanako" << endl;
}