概要

この問題は、有向非巡回グラフ（DAG）上で行われる二人ゲーム（不偏ゲーム）の勝敗を判定する問題です。ゲーム理論におけるグランディ値（Grundy value / Nim-value）の考え方を用いることで、ゲームの状態をシンプルな「Nim（石取りゲーム）」に帰着させて解くことができます。

高橋君がゲーム開始前に「ちょうど1回」行う石の除去操作によって、その後のゲームが先手（高橋君）必勝の状態になるようなマスの個数を求めます。

---

考察

1. ゲームのルールと「グランディ値」への帰着

このゲームは、プレイヤーが交互に同じルールで石を動かす「不偏ゲーム」です。また、矢印は必ず番号の大きいマスから小さいマスへ向かうため、ループ（循環）が存在しない DAG（有向非巡回グラフ）となっています。

このようなゲームは、各マスのグランディ値（\(G\)）を計算することで、有名なゲーム「Nim」として扱うことができます。

グランディ値の定義

各マス \(i\) のグランディ値 \(G[i]\) は、以下のように定義されます。 * マス \(i\) から出発する矢印が1本も存在しないとき： \(G[i] = 0\) * それ以外のとき： マス \(i\) から矢印をたどって直接遷移できるマスのグランディ値の集合に含まれない、最小の非負整数（\(\text{mex}\)） $\(G[i] = \text{mex}(\{G[v] \mid i \to v \text{ の矢印が存在する}\})\)$

例えば、マス \(i\) から \(G[v] = 0, 1, 3\) のマスへ移動できる場合、その集合 \(\{0, 1, 3\}\) に含まれない最小の非負整数は \(2\) なので、 \(G[i] = 2\) となります。

2. ゲーム全体の Nim-Sum

各マス \(i\) には \(A_i\) 個の石があります。これは「値が \(G[i]\) である Nim の山が \(A_i\) 個ある」状態と等価です。 Nim において、複数の山の状態の排他的論理和（XOR 和）を Nim-Sum と呼び、これがゲームの勝敗を決定します。

同じ値 \(G[i]\) を \(A_i\) 回 XOR することを考えます。 * \(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]\)

したがって、ゲーム開始時の全体の Nim-Sum を \(S\) とすると、 \(S\) は「石の個数 \(A_i\) が奇数であるようなマス \(i\) の \(G[i]\) の XOR 総和」となります。 $\(S = \bigoplus_{A_i \text{ is odd}} G[i]\)$

通常の Nim の定理より、「自分の手番が回ってきたときに Nim-Sum が \(0\) でなければ先手必勝、 \(0\) であれば後手必勝」となります。

3. 「除去」操作の影響

高橋君はゲーム開始前に、任意のマス \(i\) を1つ選び、そのマスの石をすべて取り除く（\(A_i\) を \(0\) にする）ことができます。 この操作によって、全体の Nim-Sum \(S\) はどのように変化するでしょうか？

• \(A_i\) が偶数のマス \(i\) を選んだ場合： もともと \(S\) の計算に \(G[i]\) は関与していなかった（偶数個なので XOR すると \(0\) になっていた）ため、石を \(0\) 個（偶数）にしても全体の Nim-Sum は \(S\) のまま変化しません。
• \(A_i\) が奇数のマス \(i\) を選んだ場合： もともと \(S\) の計算に \(G[i]\) が1回分含まれていましたが、これが \(0\) 個（偶数）になるため、全体の Nim-Sum は \(S \oplus G[i]\) に変化します。

4. 高橋君が勝てる条件

高橋君が除去を行った「後」にゲームが始まります。この時点で手番は高橋君（先手）なので、高橋君が勝つための条件は「除去後の Nim-Sum が \(0\) 以外になること」です。

除去後に Nim-Sum が \(0\) になってしまう（＝高橋君が負ける）ような「選んではいけないマス」を数え、全体のマス数 \(N\) から引くことで答えを求めます。

ケース1：初期状態の Nim-Sum \(S = 0\) のとき

• 偶数のマス \(i\) を選ぶと、除去後も Nim-Sum は \(S = 0\) のままなので負けます。
• 奇数のマス \(i\) を選ぶと、除去後の Nim-Sum は \(S \oplus G[i] = 0 \oplus G[i] = G[i]\) となります。
  • これが \(0\) になるのは \(G[i] = 0\) のとき（負け）。
  • これが \(0\) 以外になるのは \(G[i] \neq 0\) のとき（勝ち）。

したがって、勝てるマスは「\(A_i\) が奇数、かつ \(G[i] \neq 0\) であるマス」です。

ケース2：初期状態の Nim-Sum \(S \neq 0\) のとき

• 偶数のマス \(i\) を選ぶと、除去後も Nim-Sum は \(S \neq 0\) のままなので勝てます。
• 奇数のマス \(i\) を選ぶと、除去後の Nim-Sum は \(S \oplus G[i]\) となります。
  • これが \(0\) になる（負ける）のは、 \(S \oplus G[i] = 0\) すなわち \(G[i] = S\) のときだけです。

したがって、負けてしまうマスは「\(A_i\) が奇数、かつ \(G[i] = S\) であるマス」のみです。 勝てるマスの個数は、全体からこれを引いた \(N - (\text{条件を満たすマスの個数})\) となります。

---

アルゴリズム

1. 隣接リストの構築: 与えられた矢印（有向辺）からグラフを構築します。
2. グランディ値の計算: 頂点 \(1\) から \(N\) の順にループを回し、各マスのグランディ値 \(G[u]\) を決定します。
   • 問題の制約 \(U_j > V_j\) より、番号の小さいマスから順に処理することで、遷移先のマスのグランディ値がすでに計算されていることが保証されます（トポロジカルソート順での動的計画法）。
   • \(\text{mex}\) の計算は、遷移先の \(G[v]\) をマークしていくことで効率的に行います。
3. 初期 Nim-Sum \(S\) の計算: \(A_i\) が奇数であるマスの \(G[i]\) の XOR 和 \(S\) を求めます。
4. 勝てるマスのカウント:
   • \(S = 0\) の場合： \(A_i\) が奇数、かつ \(G[i] \neq 0\) であるマスの個数を数えます。
   • \(S \neq 0\) の場合： \(A_i\) が奇数、かつ \(G[i] = S\) であるマスの個数を数え、 \(N\) から引きます。

---

計算量

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

  • グランディ値の決定において、各頂点および各辺を定数回ずつ探索するため、グラフの探索に \(O(N + M)\) かかります。
  • その後の集計処理は \(O(N)\) です。
  • 全体として、制約 \(N \le 10^6, M \le 10^5\) に対して十分高速に動作します。

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

  • グラフの隣接リストに \(O(N + M)\)、グランディ値や石の数を記録する配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

• \(\text{mex}\) 計算の高速化: 各頂点 \(u\) で \(\text{mex}\) を求める際、毎回 visited 配列をゼロクリアすると \(O(N \times (\text{最大次数}))\) の最悪計算量になり TLE（実行時間制限超過）となる可能性があります。 これを防ぐため、visited[g] = u のように「どの頂点の処理で訪れたか」を記録することで、配列の初期化を不要にする工夫をしています。

• トポロジカルソートの省略: 一般の DAG ではトポロジカルソートが必要ですが、本問題では「必ず番号の大きいマスから小さいマスへ向かう」という制約があるため、単に \(1\) から \(N\) まで昇順にループを回すだけで正しくボトムアップにグランディ値を計算できます。

  ソースコード

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A_1 から A_N (1-indexed)
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(input_data[1 + i])
        
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = 1 + N + 1
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        idx += 2
        
    # 各マスのグランディ値(G)の計算
    G = [0] * (N + 1)
    visited = [0] * (M + 2)
    
    for u in range(1, N + 1):
        if not adj[u]:
            G[u] = 0
            continue
        for v in adj[u]:
            g = G[v]
            if g < M + 2:
                visited[g] = u
        mex = 0
        while visited[mex] == u:
            mex += 1
        G[u] = mex
        
    # 初期状態のグランディ値(S)の計算
    S = 0
    for i in range(1, N + 1):
        if A[i] & 1:
            S ^= G[i]
            
    # 高橋君が勝てる除去の対象マスの個数を計算
    if S == 0:
        ans = 0
        for i in range(1, N + 1):
            if (A[i] & 1) and G[i] != 0:
                ans += 1
    else:
        invalid = 0
        for i in range(1, N + 1):
            if (A[i] & 1) and G[i] == S:
                invalid += 1
        ans = N - invalid
        
    print(ans)

if __name__ == '__main__':
    solve()

---

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