公式
E - 鬼ごっこ / Tag 解説 by admin
Claude 4.6 Opus (Thinking)概要
有向グラフ上で鬼ごっこをする2人ゲームにおいて、逃げる側（高橋君）が永遠に逃げ切れるか、追う側（青木君）が必ず捕まえられるかを判定する問題です。後退解析（retrograde analysis）を用いてすべての状態の勝敗を事前計算します。
考察
ゲームの状態空間
この問題は2人完全情報ゲームです。ゲームの状態を \((s, r, t)\) で表します：
- \(s\): 高橋君の位置
- \(r\): 青木君の位置
- \(t\): ターンの段階（\(t=0\): 高橋君が動く番、\(t=1\): 青木君が動く番）
AND-OR ゲームとしての定式化
青木君（鬼）の視点で考えます：
- \(t=0\)（高橋君の番）: 高橋君は逃げたいので、捕まらない選択肢が1つでもあればそれを選ぶ。つまり青木君が勝つには全ての高橋君の選択肢が「捕獲される」状態に通じる必要がある → ANDノード
- \(t=1\)（青木君の番）: 青木君は捕まえたいので、捕まえられる選択肢が1つでもあればそれを選ぶ → ORノード
重要な気づき
状態数は \(O(N^2)\) 程度（\(N \le 500\) なので最大 \(500 \times 500 \times 2 = 500000\)）であり、後退BFSで全状態の勝敗を \(O(N^2 \cdot N)\) 程度で事前計算できます。クエリには \(O(1)\) で答えられます。
アルゴリズム
1. 状態の遷移
状態 \((s, r, 0)\) から高橋君が \(s'\) に移動すると： - \(s' = r\) なら即捕獲（ステップ2） - \(s' \neq r\) なら状態 \((s', r, 1)\) へ遷移
状態 \((s, r, 1)\) から青木君が \(r'\) に移動すると： - \(r' = s\) なら即捕獲（ステップ4） - \(r' \neq s\) なら状態 \((s, r', 0)\) へ遷移
2. 後退BFS（逆向きの探索）
初期化: 直接捕獲につながる状態をキューに入れる
- \((s, r, 0)\): 高橋君の全ての移動先が \(r\) と一致する場合（ANDノードの度数が0になる）
- \((s, r, 1)\): 青木君が \(s\) に移動できる場合（ORノードなので1つでも十分）
逆辺を辿って伝播:
- 「捕獲される」と確定した状態から逆辺を辿り、前の状態に伝播
- ANDノード: 度数を1減らし、0になったら捕獲確定
- ORノード: 即座に捕獲確定
BFS終了後、捕獲確定にならなかった状態は「逃げ切れる」
3. 逆辺の構造
- \((s, r, 1)\) の前状態: \((s', r, 0)\) ただし \(s' = s\) または \(s \in \text{adj}(s')\)（つまり \(s' \in \{s\} \cup \text{radj}(s)\)）
- \((s, r, 0)\) の前状態: \((s, r', 1)\) ただし \(r' = r\) または \(r \in \text{adj}(r')\)（つまり \(r' \in \{r\} \cup \text{radj}(r)\)）
計算量
- 時間計算量: \(O(N^3 + Q)\)
- 状態数は \(O(N^2)\)、各状態からの逆辺の探索に \(O(N)\)（逆隣接リストの長さ）
- 各クエリに \(O(1)\) で回答
- 空間計算量: \(O(N^2)\)
- 状態の捕獲フラグと度数の配列
実装のポイント
状態 \((s, r, t)\) を整数 \(s \times N \times 2 + r \times 2 + t\) にエンコードし、配列で管理する
ANDノードの初期度数は「高橋君の選択肢の数 = \(1 + \text{out\_degree}(s)\)」で、即捕獲になる選択肢（\(r\) への辺がある場合）の分をあらかじめ引いておく
逆隣接リスト
radjを事前構築し、逆辺の探索を効率化する\(s = r\) の状態はゲーム中に存在しないため、スキップする
ソースコード
import sys
from collections import deque
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
# Adjacency lists
adj = [[] for _ in range(N)] # out-neighbors
for i in range(M):
u = int(input_data[idx]) - 1; idx += 1
v = int(input_data[idx]) - 1; idx += 1
adj[u].append(v)
# State: (takahashi_pos, aoki_pos, turn)
# turn=0: Takahashi's move (step 1), then capture check (step 2)
# turn=1: Aoki's move (step 3), then capture check (step 4)
#
# This is a two-player game. Takahashi wants to escape forever, Aoki wants to capture.
# A state is "losing for Takahashi" (captured) if Aoki can force capture.
# A state is "winning for Takahashi" if Takahashi can avoid capture forever.
#
# We do backward induction from captured states.
#
# State (s, r, 0): Takahashi moves. Takahashi chooses.
# This is a Takahashi-controlled state (he wants to AVOID capture).
# Captured if ALL successors are captured. (AND node for Aoki / OR node perspective reversed)
#
# State (s, r, 1): Aoki moves. Aoki chooses.
# This is an Aoki-controlled state (he wants to FORCE capture).
# Captured if ANY successor is captured. (OR node for Aoki)
#
# Successors of (s, r, 0) [Takahashi moves]:
# Takahashi can stay or move to neighbor. After moving, check capture (step 2).
# If s' == r: captured immediately -> this successor is "captured"
# If s' != r: go to state (s', r, 1)
#
# Successors of (s, r, 1) [Aoki moves]:
# Aoki can stay or move to neighbor. After moving, check capture (step 4).
# If s == r': captured immediately -> this successor is "captured"
# If s != r': go to state (s, r', 0)
#
# We want: for query (S, R), is state (S, R, 0) captured or not?
#
# BFS from captured states backward.
# "captured" = Aoki wins.
#
# For turn=0 (Takahashi's turn, AND node for Aoki):
# All Takahashi's options must lead to capture.
# degree = number of options for Takahashi = 1 + out_degree(s)
# When all are resolved as captured, mark this state captured.
#
# For turn=1 (Aoki's turn, OR node for Aoki):
# Any one of Aoki's options leading to capture suffices.
# States: (s, r, t) where s != r (if s==r it's captured, not a real state)
# We encode state as (s, r, t) -> s*N*2 + r*2 + t
total = N * N * 2
captured = [False] * total
deg = [0] * total # only matters for turn=0 states
def encode(s, r, t):
return s * N * 2 + r * 2 + t
# Precompute degrees for turn=0 states (Takahashi's options)
# Options: stay at s, or move to each neighbor of s
# But if any option leads to s'==r, that's an immediately captured successor
for s in range(N):
out_s = len(adj[s])
for r in range(N):
if s == r:
continue
# turn=0: Takahashi moves, degree = 1 + out_degree(s)
deg[encode(s, r, 0)] = 1 + out_s
queue = deque()
# Initialize: find states whose successors include immediate captures
# For turn=0 (s, r, 0): Takahashi moves to s'. If s'==r, that option is captured.
# Since this is AND node, we decrement degree for each such option.
# Options where s'==r: stay (s==r, impossible since s!=r), or move to r if r in adj[s]
for s in range(N):
for r in range(N):
if s == r:
continue
st = encode(s, r, 0)
# Check if staying leads to capture: s==r? No since s!=r
# Check neighbors: if r in adj[s], that's one captured successor
# We need to count how many of Takahashi's moves lead to s'==r
# s' can be s (stay) or any adj[s][k]
# s==r is false. Count neighbors equal to r.
cnt = 0
for v in adj[s]:
if v == r:
cnt += 1
deg[st] -= cnt
if deg[st] == 0:
captured[st] = True
queue.append(st)
# For turn=1 (s, r, 1): Aoki moves to r'. If r'==s, captured.
# This is OR node, so any one captured successor suffices.
# r'==s: stay (r==s impossible), or s in adj[r]
for s in range(N):
for r in range(N):
if s == r:
continue
st = encode(s, r, 1)
# Check if staying leads to capture: r==s? No
# Check if any neighbor of r equals s
found = False
for v in adj[r]:
if v == s:
found = True
break
if found:
captured[st] = True
queue.append(st)
# Now BFS backwards
# We need reverse edges: for each state, who are its predecessors?
# Instead of building full reverse graph (memory heavy), we compute on the fly.
# But N=500, so total states = 500*500*2 = 500000. Reverse edges could be up to ~500000*500 which is too much.
# Let's think more carefully.
#
# Predecessors of (s, r, 1) [which is after Takahashi moved]:
# Came from (s', r, 0) where Takahashi moved from s' to s.
# s' such that s in adj[s'] (Takahashi moved s'->s), or s'=s (Takahashi stayed).
# So predecessors: {(s', r, 0) : s' = s or s in adj[s']} with s' != r
#
# Predecessors of (s, r', 0) [which is after Aoki moved, starting next turn]:
# Came from (s, r, 1) where Aoki moved from r to r'.
# r such that r' in adj[r] (Aoki moved r->r'), or r=r' (Aoki stayed).
# So predecessors: {(s, r, 1) : r = r' or r' in adj[r]} with s != r
# Precompute reverse adjacency
radj = [[] for _ in range(N)]
for s in range(N):
for v in adj[s]:
radj[v].append(s)
while queue:
st = queue.popleft()
s = st // (N * 2)
r = (st // 2) % N
t = st % 2
if t == 1:
# Predecessors are (s', r, 0) where s'=s or s in adj[s'], i.e., s' in {s} union radj[s]
# These are turn=0 (AND nodes for Aoki)
preds_s = [s] + radj[s]
for sp in preds_s:
if sp == r:
continue
pst = encode(sp, r, 0)
if not captured[pst]:
deg[pst] -= 1
if deg[pst] == 0:
captured[pst] = True
queue.append(pst)
else:
# t == 0
# Predecessors are (s, r, 1) where r such that current r' came from r
# Wait, this state is (s, r, 0). Its predecessors are states that transition TO (s,r,0).
# (s, r, 0) is reached after Aoki's move. Aoki was at some r'' and moved to r (or stayed at r).
# So predecessor state is (s, r'', 1) where r'' = r or r in adj[r''], i.e., r'' in {r} union radj[r]
# These are turn=1 (OR nodes for Aoki)
preds_r = [r] + radj[r]
for rp in preds_r:
if s == rp:
continue
pst = encode(s, rp, 1)
if not captured[pst]:
captured[pst] = True
queue.append(pst)
Q = int(input_data[idx]); idx += 1
out = []
for _ in range(Q):
s = int(input_data[idx]) - 1; idx += 1
r = int(input_data[idx]) - 1; idx += 1
if captured[encode(s, r, 0)]:
out.append("NO")
else:
out.append("YES")
sys.stdout.write('\n'.join(out) + '\n')
main()
この解説は claude4.6opus-thinking によって生成されました。
投稿日時:
最終更新: