概要

各石は矢印に沿って小さい番号のマスへ移動する独立なゲームです。
各マスの Grundy 数を求め、全体の xor が \(0\) でないかどうかで勝敗を判定します。

考察

このゲームは、石が複数ある不偏ゲームです。
各石は他の石に影響を与えず、現在いるマスから矢印に沿って移動するだけなので、各石を独立したゲームとして考えられます。

1 個の石だけを考える

マス \(u\) に石が 1 個あるとします。
この石は、\(u\) から出ている矢印 \((u, v)\) を選んでマス \(v\) に移動できます。

このようなゲームでは、各マス \(u\) に対して Grundy 数 \(g_u\) を定義できます。

\[ g_u = \mathrm{mex}\{ g_v \mid u \to v \text{ という矢印がある} \} \]

ここで \(\mathrm{mex}\) は「含まれていない最小の非負整数」です。

例えば、移動先の Grundy 数が \(\{0, 1, 3\}\) なら、mex は \(2\) です。

矢印は必ず \(U_j > V_j\)、つまり大きい番号から小さい番号へ向かうので、マス \(1\) から順に見ていけば、移動先の Grundy 数はすでに計算済みです。

複数の石がある場合

複数の独立したゲームの合成では、Sprague-Grundy の定理より、全体の状態は各石の Grundy 数の xor で表されます。

つまり、全体の xor を \(X\) とすると、

• \(X = 0\) なら後手必勝
• \(X \neq 0\) なら先手必勝

です。

マス \(i\) に石が \(A_i\) 個あり、その Grundy 数が \(g_i\) であるとします。
このマスからの寄与は

\[ \underbrace{g_i \oplus g_i \oplus \cdots \oplus g_i}_{A_i \text{ 個}} \]

です。

同じ値を 2 回 xor すると消えるので、

• \(A_i\) が偶数なら寄与は \(0\)
• \(A_i\) が奇数なら寄与は \(g_i\)

になります。

したがって、石の個数は偶奇だけ見れば十分です。

初期状態の xor は

\[ X = \bigoplus_{i : A_i \text{ が奇数}} g_i \]

です。

除去の影響

ゲーム開始前に、マス \(i\) の石をすべて取り除きます。

このとき、全体 xor からマス \(i\) の寄与が消えます。

• \(A_i\) が偶数なら、もともとの寄与は \(0\) なので xor は変わりません
• \(A_i\) が奇数なら、寄与 \(g_i\) が消えるので xor は \(X \oplus g_i\) になります

よって、マス \(i\) を除去した後の xor は

\[ X_i = \begin{cases} X \oplus g_i & (A_i \text{ が奇数}) \\ X & (A_i \text{ が偶数}) \end{cases} \]

となります。

高橋君が勝てるのは、除去後の xor が \(0\) でない場合です。
したがって、各マス \(i\) について \(X_i \neq 0\) かを判定すればよいです。

素朴に各除去候補ごとにゲーム全体を再計算すると \(O(N(N+M))\) などになり、\(N \leq 10^6\) では間に合いません。
しかし、Grundy 数と初期 xor を一度だけ計算すれば、各マスの判定は \(O(1)\) でできます。

アルゴリズム

1. 各 \(A_i\) について偶奇だけを保存する。
2. 矢印を隣接リストで管理する。
3. マス番号の小さい順に Grundy 数を計算する。
   • 矢印は大きい番号から小さい番号へ向かうため、マス \(u\) を処理するとき、移動先 \(v\) の Grundy 数はすでに分かっている。
   • 移動先の Grundy 数を集め、その mex を \(g_u\) とする。
4. \(A_i\) が奇数なら、初期 xor に \(g_i\) を xor する。
5. 各マス \(i\) について、除去後の xor を求める。
   • \(A_i\) が奇数なら \(X \oplus g_i\)
   • \(A_i\) が偶数なら \(X\)
6. 除去後の xor が \(0\) でないマスの個数を数える。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

Grundy 数の計算では mex を高速に求める必要があります。

各マスごとに配列を初期化すると遅くなるため、seen 配列と stamp を使っています。

++stamp;

for (int e = head[u]; e != -1; e = nxt[e]) {
    int g = grundy[to[e]];
    seen[g] = stamp;
}

int mex = 0;
while (seen[mex] == stamp) mex++;

このようにすると、毎回 seen 配列全体を初期化せずに済みます。

また、マス \(u\) の Grundy 数は、出次数を \(d\) とすると高々 \(d\) なので、全体で \(O(N+M)\) に収まります。

ソースコード

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

class FastScanner {
    static constexpr int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    char getChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return '\0';
        }
        return buf[idx++];
    }

public:
    template <class T>
    bool read(T &out) {
        char c;
        T sign = 1;
        T num = 0;

        c = getChar();
        if (c == '\0') return false;

        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
            if (c == '\0') return false;
        }

        if (c == '-') {
            sign = -1;
            c = getChar();
        }

        while (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            c = getChar();
        }

        out = num * sign;
        return true;
    }
};

int main() {
    FastScanner fs;

    int N, M;
    fs.read(N);
    fs.read(M);

    vector<unsigned char> odd(N + 1);
    for (int i = 1; i <= N; i++) {
        long long x;
        fs.read(x);
        odd[i] = (unsigned char)(x & 1);
    }

    vector<int> head(N + 1, -1);
    vector<int> to(M), nxt(M);

    for (int e = 0; e < M; e++) {
        int U, V;
        fs.read(U);
        fs.read(V);
        to[e] = V;
        nxt[e] = head[U];
        head[U] = e;
    }

    vector<int> grundy(N + 1, 0);
    vector<int> seen(M + 2, 0);
    int stamp = 0;

    int xr = 0;

    for (int u = 1; u <= N; u++) {
        ++stamp;

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int g = grundy[to[e]];
            if (g <= M) seen[g] = stamp;
        }

        int mex = 0;
        while (seen[mex] == stamp) mex++;

        grundy[u] = mex;

        if (odd[u]) xr ^= mex;
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        int after = xr;
        if (odd[i]) after ^= grundy[i];
        if (after != 0) ans++;
    }

    printf("%lld\n", ans);
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。