Day 013-Q2 — Algorithmic Game Theory（複合ゲーム）

問題

N 個の独立なゲームが同時進行。各ゲーム i は DAG $G_i$ で表され、駒の位置 $v_i$ から2人が交互に動かす。動かせなくなったら負け。全ゲームの Grundy 値の XOR が 0 でないとき先手必勝。Grundy 値、勝者、先手必勝なら初手を出力せよ。

制約

入出力例

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

Grundy values: 1 2 2
XOR: 1
First player wins
Move in game 1 to vertex 2

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from functools import lru_cache
input = sys.stdin.readline

def solve():
    N = int(input())
    games = []
    for _ in range(N):
        V, E, s = map(int, input().split())
        graph = [[] for _ in range(V + 1)]
        for _ in range(E):
            u, v = map(int, input().split())
            graph[u].append(v)
        games.append((V, s, graph))

    def compute_grundy(graph, V):
        memo = {}
        def grundy(v):
            if v in memo:
                return memo[v]
            reachable = set()
            for w in graph[v]:
                reachable.add(grundy(w))
            m = 0
            while m in reachable:
                m += 1
            memo[v] = m
            return m
        all_g = {}
        for v in range(1, V + 1):
            all_g[v] = grundy(v)
        return all_g

    grundy_vals = []
    all_g_maps = []
    for V, s, graph in games:
        g_map = compute_grundy(graph, V)
        grundy_vals.append(g_map[s])
        all_g_maps.append(g_map)

    total_xor = 0
    for g in grundy_vals:
        total_xor ^= g

    print(f"Grundy values: {' '.join(map(str, grundy_vals))}")
    print(f"XOR: {total_xor}")

    if total_xor == 0:
        print("Second player wins")
    else:
        print("First player wins")
        for i, (gv, (V, s, graph), g_map) in enumerate(zip(grundy_vals, games, all_g_maps)):
            target = total_xor ^ gv
            for w in graph[s]:
                if g_map[w] == target:
                    print(f"Move in game {i+1} to vertex {w}")
                    return

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• DAG でない循環ゲームへの対応

自己評価

自分の回答

気づき・メモ