勝敗判定基準 5-n

\(2n\) 個の奇成分がどれもひとつの頂点からなるとき、それらを \(2\) つずつ組として互いの頂点を結び、新たな \(n\) 個の偶成分にしたのち勝敗判定基準 \(3\) を用いることで勝敗を判定することができる。

すべての正整数 \(n\) にわたる勝敗判定基準 4-n の主張をまとめて、より完結に記述することができます。

勝敗判定基準 4

大きさが \(3\) 以上の奇成分が \(1\) つか \(2\) つであるとき、先手必勝である。

勝敗判定基準 4 の結果に補題を適用して、大きさが \(3\) 以上の奇成分を \(1\) つか \(2\) つにするような手を打つことはできないとしておきます。

はじめに大きさが \(3\) 以上の奇成分が \(3\) つ以上ある場合に、終局時のグラフが満たすべき性質を考えます。

奇成分の個数を \(1\) 手で \(3\) つ以上減らすことはできないため、終局時にも奇成分は \(3\) つ以上存在します。

グラフに偶成分が存在するとき、それと他の連結成分をつなぐ合法手が存在するので、終局時のグラフには偶成分は存在しません。

また、グラフのある連結成分が完全二部グラフでないとき、連結性を変えないまま打てる合法手があるので、終局時のグラフの連結成分はすべて完全二部グラフです。

以上より、終局時のグラフのすべての連結成分は奇成分であり、かつ完全二部グラフになっています。 つまり、終局時のグラフの辺の本数は偶数本です。

よって次のことがわかります。

勝敗判定基準 6

大きさが \(3\) 以上の奇成分が \(3\) つ以上あるとき、

• \(M\) が偶数なら、高橋くんが勝つ。
• \(M\) が奇数なら、青木くんが勝つ。

ここまでの勝敗判定基準をまとめると、以下のようになります。

勝敗判定基準

1. （勝敗判定基準 1）\(N\) が奇数のとき、
   • \(M\) が偶数なら、高橋くんが勝つ。
   • \(M\) が奇数なら、青木くんが勝つ。
2. （勝敗判定基準 6）\(N\) が偶数で、大きさが \(3\) 以上の奇成分が \(3\) つ以上あるとき、
   • \(M\) が偶数なら、高橋くんが勝つ。
   • \(M\) が奇数なら、青木くんが勝つ。
3. （勝敗判定基準 4）\(N\) が偶数で、大きさが \(3\) 以上の奇成分が \(1\) つか \(2\) つだけあるとき、先手必勝。
4. （勝敗判定基準 3, 5-n）\(N\) が偶数で、大きさが \(3\) 以上の奇成分が存在しないとき、偶成分のうち極大な独立集合の大きさが奇数であるような連結成分の個数を \(O\) 、奇成分の個数を \(I\) として、
   • \(M+O+I/2\) が偶数なら、高橋くんが勝つ。
   • \(M+O+I/2\) が奇数なら、青木くんが勝つ。

これらを実装することで、この問題に正解することができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <ranges>
#include <numeric>

int main() {
    using namespace std;
    unsigned N, M;
    cin >> N >> M;

    // 1. N が奇数のとき、M の偶奇から終局時の手番が確定する
    if (N & 1) {
        cout << (M & 1 ? "Aoki" : "Takahashi") << endl;
        return 0;
    }

    // N が偶数のとき

    vector<pair<unsigned, unsigned>> edges(M);

    for (auto&& [u, v] : edges) {
        cin >> u >> v;
        --u;
        --v;
    }

    // サイズが 3 以上の奇成分の個数を数える
    unsigned big_odd_component_count{};
    // 2O + I を数える
    unsigned odd_count{};

    // 頂点倍加して union-find
    vector<unsigned long> uf(2 * N), sz(2 * N, 1);
    ranges::fill(sz | views::take(N), 524289);
    iota(begin(uf), end(uf), 0U);
    const auto find{[&uf](auto i) { while (i != uf[i])i = uf[i] = uf[uf[i]]; return i; }};
    const auto unite{[&uf, &sz, find](auto i, auto j) {
        i = find(i);
        j = find(j);
        if (i == j) return;
        if (sz[i] < sz[j])swap(i, j);
        uf[j] = i;
        sz[i] += sz[j];
    }};

    for (const auto& [u, v] : edges) {
        unite(u, v + N);
        unite(u + N, v);
    }

    for (unsigned i{}; i < N; ++i)
        // 連結成分のうち、片方の極大な独立集合をみる
        if (i == find(i) && i < find(i + N)) {
            // 1 点からなるなら、I++
            if (sz[i] == 524289)
                ++odd_count;
            // 3 点以上からなる奇成分なら、それをカウント
            else if (sz[i] % 2) {
                // 2. 大きい奇成分が 3 つ以上なら、M の偶奇で（ルール変更後のゲームでの）終局時の手番が確定する
                if (++big_odd_component_count > 2) {
                    cout << (M & 1 ? "Aoki" : "Takahashi") << endl;
                    return 0;
                }
            }
            // 偶成分なら、極大な独立集合のサイズの 2 倍を足しておく
            else
                odd_count += sz[i] / 262144;
        }

    // 3. 大きい奇成分が 1 つか 2 つなら、先手必勝
    if (big_odd_component_count) {
        cout << "Aoki" << endl;
        return 0;
    }
    
    // 4. M + O + I/2 の偶奇で最終的な手番が確定する
    cout << ((M ^ odd_count / 2) & 1 ? "Aoki" : "Takahashi") << endl;

    return 0;
}