概要

この問題は、DAG（有向非巡回グラフ）上で石を移動させる二人対戦ゲームです。 各石は独立に移動させることができるため、ゲーム理論における「Nim（ニム）」および「Grundy値（グランディ数）」の考え方を適用することで、効率的に解くことができます。

---

考察

1. ゲームを独立な「石」に分解する

このゲームでは、プレイヤーは1つの石を選んで矢印の先に進めます。それぞれの石の移動は他の石の移動に一切影響を与えません。 このように、複数の独立したゲームが並行して進行し、全体として1つのゲームを構成するものを「ゲームの和（多山Nim）」と呼びます。

この性質から、「盤面全体の勝敗状態は、それぞれの石が置かれているマスのGrundy値のXOR和（排他的論理和）によって決定される」という性質（Sprague-Grundyの定理）が成り立ちます。

2. マス \(i\) のGrundy値 \(G[i]\) の定義

1つの石がマス \(i\) にあるときのゲームのGrundy値 \(G[i]\) は、以下のように再帰的に定義されます。

\[G[i] = \text{mex}(\{ G[v] \mid \text{マス } i \text{ からマス } v \text{ への矢印が存在する} \})\]

ここで、\(\text{mex}(S)\) は集合 \(S\) に含まれない最小の非負整数（\(0, 1, 2, \ldots\)）を表します。 矢印は必ず番号の大きいマスから小さいマスへ向かう（\(U_j > V_j\)）ため、このグラフはDAGであり、マス \(1\) から順に \(G[i]\) を確定させていくことができます。

3. 同じマスに複数の石がある場合

マス \(i\) に \(A_i\) 個の石があるとき、これらは「Grundy値が \(G[i]\) である独立した \(A_i\) 個のゲーム」とみなせます。 同じ値のXOR和は、偶数個なら \(0\)、奇数個ならその値自身になります。

• \(A_i\) が偶数の場合： \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = 0\)
• \(A_i\) が奇数の場合： \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = G[i]\)

したがって、ゲーム全体の初期状態のXOR和 \(X\) は、「石の個数 \(A_i\) が奇数であるマス \(i\) の \(G[i]\) の総XOR和」となります。

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

4. 高橋君の「除去」操作の影響

ゲーム開始前に、高橋君は任意のマス \(k\) を1つ選び、そのマスの石をすべて取り除きます（\(A_k\) を \(0\)、すなわち偶数個にします）。 この「除去」を行った後のゲーム全体のXOR和を \(X'_k\) とすると、以下のように表せます。

• \(A_k\) がもともと奇数だった場合： マス \(k\) の寄与 \(G[k]\) が消えるため、除去後のXOR和は \(X'_k = X \oplus G[k]\) となります。
• \(A_k\) がもともと偶数だった場合： もともと全体のXOR和 \(X\) に寄与していなかったため、除去後のXOR和は \(X'_k = X\) のままです。

5. 勝敗条件

先手（高橋君）が最適な行動をとって勝てる条件は、「ゲーム開始時点（除去を行った直後）のXOR和が \(0\) 以外の値であること」です。 したがって、各 \(k \in \{1, \dots, N\}\) について \(X'_k \neq 0\) となるような \(k\) の個数を数えれば、それが求める答えとなります。

---

アルゴリズム

1. Grundy値の計算: マス \(1\) から \(N\) まで順番に、そのマスから遷移できるマスのGrundy値の \(\text{mex}\) を求めて \(G[i]\) を計算します。 このとき、問題の条件（\(U_j > V_j\)）より、遷移先のGrundy値はすべて計算済みであることが保証されています（トポロジカルソートが不要です）。

2. 全体のXOR和の計算: \(A_i\) が奇数であるすべての \(i\) について、\(G[i]\) のXOR和 \(X\) を計算します。

3. 除去のシミュレーション: 各マス \(k\) について、除去後のXOR和 \(X'_k\) を計算します。

   • \(A_k \pmod 2 == 1\) ならば、 \(X'_k = X \oplus G[k]\)
   • \(A_k \pmod 2 == 0\) ならば、 \(X'_k = X\)

\(X'_k \neq 0\) となる \(k\) の個数をカウントして出力します。

---

計算量

• 時間計算量: \(O(N + M)\)
  • Grundy値の計算において、各頂点と各辺を走査するため、全体で \(O(N + M)\) 時間で処理できます。
  • 各 \(k\) に対する除去後のXOR和の判定は \(O(1)\) で行えるため、判定パートは \(O(N)\) 時間です。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リスト adj を保持するのに \(O(N + M)\)、Grundy値を保持する配列 G や marked 配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

• \(\text{mex}\) の高速な計算: 各マス \(i\) で \(\text{mex}\) を求める際、毎回マーク用配列（marked）を false で初期化すると最悪 \(O(N^2)\) の時間がかかってしまいます。 これを防ぐため、「遷移先のマーク処理」→「\(\text{mex}\) の探索」→「遷移先のマーク解除」 とすることで、マーク用配列の初期化を \(O(\text{出次数})\) で行い、全体で \(O(N + M)\) を達成しています。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> G(N + 1, 0);
    vector<bool> marked(N + 2, false);

    // Compute Grundy values in O(N + M) time
    for (int i = 1; i <= N; ++i) {
        for (int v : adj[i]) {
            int g = G[v];
            if (g < (int)marked.size()) {
                marked[g] = true;
            }
        }
        int mex = 0;
        while (marked[mex]) {
            mex++;
        }
        G[i] = mex;
        // Clean up the marked array for the next vertices
        for (int v : adj[i]) {
            int g = G[v];
            if (g < (int)marked.size()) {
                marked[g] = false;
            }
        }
    }

    // Calculate the initial XOR-sum of the game
    int X = 0;
    for (int i = 1; i <= N; ++i) {
        if (A[i] % 2 == 1) {
            X ^= G[i];
        }
    }

    // Count the number of valid choices for removal
    int ans = 0;
    for (int k = 1; k <= N; ++k) {
        int X_prime = X;
        if (A[k] % 2 == 1) {
            X_prime ^= G[k];
        }
        if (X_prime != 0) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。