Day 040-Q1 — Grundy値逆解析・組み合わせゲーム完全解析

2026-05-23 赤色 Master / Phase 8+ ★★★★★★★★★ Sprague-Grundy + prefix XOR

問題

$N$ 頂点の DAG $G$ が与えられる。各頂点の Grundy 値 $G(v) = \text{mex}(\{G(w) \mid v \to w\})$ を計算し、$Q$ クエリ $(l, r)$ に対してトポロジカル順で $l$ 番目から $r$ 番目の頂点の Grundy 値の XOR 総和を答えよ。

制約

$1 \le N \le 5 \times 10^4$
$0 \le M \le 2 \times 10^5$
$1 \le Q \le 10^5$
DAG 保証
時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

5 5
1 2
1 3
2 4
3 4
4 5
3
1 3
2 5
1 5

出力例 1

3
2
1

概念図: Grundy値の計算フロー

1 2 3 4 5 G=2 G=1 G=0 G=0 G=0 mex の計算例: 頂点1: 後継={2,3}, G={1,0} mex({0,1}) = 2

ヒント（段階的開示）

ヒント1: 方向性
トポロジカルソートの逆順（葉から根へ）に mex を計算すると Grundy 値が求まる。その後は prefix XOR で区間 XOR クエリを O(1) で処理できる。
ヒント2: mex の計算
mex(S) は集合 S に含まれない最小の非負整数。出次数 0 の頂点の Grundy 値は 0。各頂点は後継の Grundy 値集合の mex を取る。N が大きいので mex の計算には set を使う。
ヒント3: 実装骨格 
# トポロジカルソート後、逆順処理
for v in reversed(topo):
    s = {grundy[w] for w in graph[v]}
    mx = 0
    while mx in s: mx += 1
    grundy[v] = mx

# prefix XOR
prefix = [0] * (N + 1)
for i, v in enumerate(topo):
    prefix[i+1] = prefix[i] ^ grundy[v]

# クエリ l..r (1-indexed)
ans = prefix[r] ^ prefix[l-1]

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    in_deg = [0] * (N+1)
    for _ in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)
        in_deg[v] += 1

    # トポロジカルソート (Kahn's algorithm)
    dq = deque(i for i in range(1, N+1) if in_deg[i] == 0)
    topo = []
    while dq:
        v = dq.popleft()
        topo.append(v)
        for w in graph[v]:
            in_deg[w] -= 1
            if in_deg[w] == 0:
                dq.append(w)

    # Grundy値の計算（逆順）
    grundy = [0] * (N+1)
    for v in reversed(topo):
        s = {grundy[w] for w in graph[v]}
        mx = 0
        while mx in s:
            mx += 1
        grundy[v] = mx

    # prefix XOR（トポロジカル順インデックス）
    prefix = [0] * (N+1)
    for i, v in enumerate(topo):
        prefix[i+1] = prefix[i] ^ grundy[v]

    Q = int(input())
    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        out.append(prefix[r] ^ prefix[l-1])
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1Grundy 値の定義
Sprague-Grundy 定理: DAG ゲームの各頂点 $v$ の Grundy 値 $G(v) = \text{mex}(\{G(w) \mid v \to w \in E\})$。出次数 0 の頂点は $G(v) = 0$（敗北点）。
2トポロジカルソート
Kahn's Algorithm で入次数 0 の頂点から BFS。逆順処理で葉 → 根の順に mex を計算。
3mex の計算
各頂点の後継 Grundy 値を set に収集し、0 から順に含まれない最小値を探す。最大 mex 値は出次数以下なので O(deg(v)) で計算。
4prefix XOR
トポロジカル順に並べた Grundy 値列に対して prefix XOR 配列を構築。区間 [l,r] の XOR は prefix[r] ^ prefix[l-1] で O(1)。
5計算量
全体: $O(N + M + Q)$。mex 計算は全辺で O(M) 合計。

計算量

トポロジカルソート: $O(N + M)$
全 mex 計算: $O(N + M)$（全辺 O(M) で set 構築）
prefix XOR 構築: $O(N)$
クエリ: $O(1)$ per query
合計: $O(N + M + Q)$

よくあるミス

ミス原因正しい書き方
mex 計算で無限ループset に基づく判定while mx in s: mx += 1
トポロジカル順と逆順を混同Grundy 値は逆順（葉→根）で計算for v in reversed(topo)
prefix XOR の 0-indexed/1-indexed ずれクエリで l-1 を忘れprefix[r] ^ prefix[l-1]
出次数 0 でも mex 計算空集合の mex = 0空集合チェック不要（mx=0 が正解）

次のステップ

  • 発展: 複数のゲームを同時プレイ（XOR で Grundy 値を結合）
  • 応用: Misère Nim への変換（Grundy 値が全 0 でない場合の勝利条件変更）
  • 類題: DAG ゲームの先手必勝条件と最適手の復元

自己評価