概要

これは DAG（一方通行の矢印）上で石を動かす二人ゲームで、Sprague–Grundy の定理（Nim 理論） を用いて勝敗を判定する問題です。高橋君がちょうど 1 回行う「除去」によって勝てるようになるマスの個数を数えます。

考察

ゲームの本質を Grundy 数で捉える

矢印は必ず番号の大きいマスから小さいマスへ向かう（\(U_j > V_j\)）ので、石を動かし続けても同じマスに戻ることはなく、ゲームは必ず終了します。最後に操作できなくなった人が負け（通常の Nim ルール）です。

このゲームは、各石が独立に動く「ゲームの直和」とみなせます。1 個の石をマス \(i\) に置いた状態の Grundy 数を \(g[i]\) とすると、次の漸化式で求まります。

\[g[i] = \mathrm{mex}\{\, g[v] \mid \text{マス } i \text{ から } v \text{ への矢印がある} \,\}\]

ここで \(\mathrm{mex}(S)\) は集合 \(S\) に含まれない最小の非負整数です。矢印が 1 本も出ていないマスは操作できないので \(g[i] = 0\) となります。

複数の石とパリティ

マス \(i\) には \(A_i\) 個の石があります。同じマスにある石はすべて Grundy 数 \(g[i]\) を持つので、直和の Grundy 数（XOR）への寄与は

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

となります。同じ値を偶数回 XOR すると \(0\)、奇数回なら \(g[i]\) になるので、

• \(A_i\) が偶数なら寄与は \(0\)
• \(A_i\) が奇数なら寄与は \(g[i]\)

つまり、盤面全体の Grundy 数は

\[\text{total} = \bigoplus_{i:\, A_i \text{ が奇数}} g[i]\]

であり、\(\text{total} \neq 0\) のとき先手（高橋君）の勝ちです。

除去操作の影響

高橋君はちょうど 1 回、あるマス \(i\) の石をすべて取り除きます（\(A_i \to 0\)）。\(0\) は偶数なので、除去後のパリティは「偶数」になります。これにより XOR がどう変わるかを場合分けします。

• もともと \(A_i\) が偶数のマスを除去：寄与はもともと \(0\) で、除去後も \(0\) のまま。XOR は \(\text{total}\) で変わらない。 → 勝てる条件は \(\text{total} \neq 0\)
• もともと \(A_i\) が奇数のマスを除去：寄与 \(g[i]\) が消えるので、新しい XOR は \(\text{total} \oplus g[i]\)。 → 勝てる条件は \(\text{total} \oplus g[i] \neq 0\)、すなわち \(g[i] \neq \text{total}\)

これらを満たすマスの個数を数えれば答えになります。

素朴な実装の落とし穴

\(N\) が最大 \(10^6\)、\(A_i\) が最大 \(10^9\) と大きいため、石を 1 個ずつシミュレートするのは不可能です。しかし上記の通り 重要なのは \(A_i\) の偶奇だけ なので、各 \(A_i\) を読み取った時点で偶奇情報のみ保持すれば十分です。

アルゴリズム

1. 各 \(A_i\) の偶奇を記録し、偶数マスの個数 cntEven を数える。
2. 矢印を CSR 形式（隣接リストを 1 本の配列に詰める形）で格納する。\(V_j < U_j\) なので、マス番号の小さい順に \(g\) を計算すれば、参照する \(g[v]\) はすでに確定している。
3. 各マス \(u\) について、出辺の本数を \(d\) とすると、\(\mathrm{mex}\) に影響するのは値が \(d\) 以下の \(g[v]\) だけ（\(\mathrm{mex}\) は最大でも \(d\)）。これを利用してフラグ配列で \(\mathrm{mex}\) を \(O(d)\) で計算する。
4. \(A_i\) が奇数のマスについて \(g[i]\) を XOR し \(\text{total}\) を求める。
5. 上の場合分けに従って答えを集計する。
   • \(\text{total} \neq 0\) なら偶数マス全部（cntEven）を加算
   • 奇数マスのうち \(g[i] \neq \text{total}\) となるものを加算

mex 計算の工夫

\(\mathrm{mex}\) を求める際、フラグ配列を毎回 \(0\) クリアすると \(O(N \cdot \text{maxdeg})\) かかる恐れがあります。そこで、

• フラグを立てるのは値が \(d\) 以下の \(g[v]\) のみ
• 計算後、同じ出辺をもう一度走査して立てたフラグだけ戻す

とすることで、各マスの処理が出辺数に比例した \(O(d)\) で済み、全体で \(O(M)\) になります。

計算量

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

実装のポイント

• \(A_i \le 10^9\) なので 64bit で読み取り、偶奇 (a & 1) だけ保存すればメモリを節約できる（\(N \le 10^6\)）。

• 矢印の格納は CSR（累積和でオフセットを作る）を使うと、隣接リストの vector を \(N\) 本持つよりメモリ・速度ともに有利。

• \(g\) の計算はマス番号 \(1\) から \(N\) へ昇順に行えば、\(V_j < U_j\) の制約により参照先がすでに計算済みであることが保証される。

• \(\mathrm{mex}\) 用フラグ配列は最大次数 \(+2\) まで確保すれば足りる。値が次数を超える \(g[v]\) は \(\mathrm{mex}\) に影響しないので無視してよい。

• 入力サイズが大きいので、高速な入力処理（自前のバッファ読み込み）を用いると安全。

  ソースコード

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

static char buf[1 << 25];
int bufpos = 0, buflen = 0;
inline int readChar() {
    if (bufpos == buflen) {
        buflen = (int)fread(buf, 1, sizeof(buf), stdin);
        bufpos = 0;
        if (buflen == 0) return -1;
    }
    return buf[bufpos++];
}
inline long long readInt() {
    int c = readChar();
    while (c != '-' && (c < '0' || c > '9')) c = readChar();
    bool neg = false;
    if (c == '-') { neg = true; c = readChar(); }
    long long x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = readChar(); }
    return neg ? -x : x;
}

int main() {
    int N = (int)readInt();
    int M = (int)readInt();

    vector<char> parity(N + 1, 0); // A_i の偶奇
    int cntEven = 0;
    for (int i = 1; i <= N; i++) {
        long long a = readInt();
        if (a & 1LL) parity[i] = 1;
        else cntEven++;
    }

    // 出辺の格納（CSR）
    vector<int> U(M), V(M);
    vector<int> deg(N + 2, 0);
    for (int j = 0; j < M; j++) {
        int u = (int)readInt();
        int v = (int)readInt();
        U[j] = u; V[j] = v;
        deg[u]++;
    }
    vector<int> start(N + 2, 0);
    for (int i = 1; i <= N + 1; i++) start[i] = start[i - 1] + deg[i - 1];
    // start[i] は CSR の開始位置（マス i は start[i]..start[i+1]）
    vector<int> adj(M);
    {
        vector<int> pos(N + 2);
        for (int i = 0; i <= N + 1; i++) pos[i] = start[i];
        for (int j = 0; j < M; j++) {
            int u = U[j];
            adj[pos[u]++] = V[j];
        }
    }

    vector<int> g(N + 1, 0);
    // mex 用の作業領域
    vector<int> markVal; // 訪問したインデックス
    vector<char> mark;   // mex用フラグ
    // mark は最大次数+1 まで使う。動的に確保。
    int maxdeg = 0;
    for (int i = 1; i <= N; i++) maxdeg = max(maxdeg, deg[i]);
    mark.assign(maxdeg + 2, 0);

    for (int u = 1; u <= N; u++) {
        int s = start[u], e = start[u + 1];
        if (s == e) { g[u] = 0; continue; }
        int d = e - s;
        // 値が d 以下のものだけ mex に影響
        for (int k = s; k < e; k++) {
            int gv = g[adj[k]];
            if (gv <= d) mark[gv] = 1;
        }
        int m = 0;
        while (m <= d && mark[m]) m++;
        g[u] = m;
        // リセット
        for (int k = s; k < e; k++) {
            int gv = g[adj[k]];
            if (gv <= d) mark[gv] = 0;
        }
    }

    // total XOR （A_i が奇数のマスの g[i] の XOR）
    long long total = 0;
    for (int i = 1; i <= N; i++) {
        if (parity[i]) total ^= g[i];
    }

    long long ans = 0;
    // 偶数マス：除去後 XOR は total
    if (total != 0) ans += cntEven;
    // 奇数マス：除去後 XOR は total ^ g[i]
    for (int i = 1; i <= N; i++) {
        if (parity[i]) {
            if ((long long)g[i] != total) ans++;
        }
    }

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

---

この解説は claude4.8opus-high によって生成されました。