E - 石移動ゲーム / Stone Moving Game 解説 by admin
gpt-5.5-high概要
各石を「DAG 上を移動する独立したゲーム」とみなし、Sprague-Grundy 数（SG 値）を計算します。
除去後の全体の XOR（ニム和）が \(0\) でなければ先手の高橋君が勝てるので、各マスを除去したときのニム和を効率よく判定します。
考察
1. 石 1 個のゲームとして見る
マス \(i\) に石が 1 個あるとき、その石は矢印に沿って移動できます。
矢印は必ず番号の大きいマスから小さいマスへ向かうので、グラフは DAG です。
このようなゲームでは、各マス \(i\) に対して SG 値 \(G_i\) を定義できます。
\(G_i\) は、マス \(i\) から 1 手で移動できる先の SG 値たちの mex です。
\[ G_i = \mathrm{mex}(\{G_v \mid i \to v\}) \]
ここで mex とは「集合に含まれない最小の非負整数」です。
例えば、移動先の SG 値が \(\{0, 1, 3\}\) なら、含まれていない最小の非負整数は \(2\) なので、mex は \(2\) です。
矢印は \(U_j > V_j\) を満たすため、マス番号の小さい順に見ていけば、移動先の SG 値はすでに計算済みです。
2. 複数の石がある場合
このゲームでは、1 回の操作で動かす石は 1 個だけです。
したがって、複数の石がある状態は、それぞれの石による独立なゲームの和とみなせます。
SG 定理より、全体の勝敗は各石の SG 値の XOR で決まります。
全体のニム和を \(X\) とすると、
- \(X \neq 0\) なら先手勝ち
- \(X = 0\) なら後手勝ち
です。
マス \(i\) に \(A_i\) 個の石があり、それぞれ SG 値は \(G_i\) です。
同じ値を偶数回 XOR すると消えるので、重要なのは \(A_i\) の偶奇だけです。
つまり、初期状態のニム和は
\[ X = \bigoplus_{i : A_i \text{ が奇数}} G_i \]
です。
\(A_i\) が偶数なら、そのマスの石全体の XOR への寄与は \(0\) になります。
3. 除去の影響
高橋君は、ゲーム開始前にちょうど 1 つのマス \(i\) を選び、そのマスの石をすべて除去します。
除去前のニム和を \(X\) とします。
\(A_i\) が偶数の場合
もともとマス \(i\) の寄与は XOR 上では \(0\) です。
除去してもニム和は変わりません。
\[ X' = X \]
\(A_i\) が奇数の場合
もともとマス \(i\) は \(G_i\) を 1 回分だけ XOR に寄与していました。
除去するとその寄与が消えるので、
\[ X' = X \oplus G_i \]
となります。
除去後に高橋君が勝てる条件は \(X' \neq 0\) です。
4. 場合分け
奇数個の石があるマスのうち、SG 値が \(g\) であるものの個数を freq[g] とします。
また、奇数個の石があるマスの総数を odd_count とします。
初期ニム和 \(X = 0\) の場合
\(A_i\) が偶数のマスを除去しても \(X'=0\) のままなので負けです。
\(A_i\) が奇数のマスを除去すると、
\[ X' = 0 \oplus G_i = G_i \]
です。
したがって、勝てるのは \(G_i \neq 0\) のマスを除去した場合です。
よって答えは、
\[ \text{odd\_count} - \text{freq}[0] \]
です。
初期ニム和 \(X \neq 0\) の場合
\(A_i\) が偶数のマスを除去すると、ニム和は \(X\) のままなので必ず勝ちです。
\(A_i\) が奇数のマスを除去すると、
\[ X' = X \oplus G_i \]
です。
これが \(0\) になるのは、
\[ G_i = X \]
のときだけです。
したがって、負けになるのは「\(A_i\) が奇数かつ \(G_i = X\)」のマスだけです。
答えは、
\[ N - \text{freq}[X] \]
です。
ただし、SG 値は最大でも \(M\) 以下なので、\(X > M\) の場合は \(\text{freq}[X]=0\) とみなせます。
この場合、すべてのマスを除去しても高橋君が勝てるので答えは \(N\) です。
素朴な方法が難しい理由
各マスを除去候補として、毎回ゲーム全体の勝敗を再計算すると \(O(N^2)\) 以上かかる可能性があります。
また、\(A_i\) は最大 \(10^9\) なので、石 1 個ずつを扱うこともできません。
そこで、
- 各マスの SG 値を一度だけ計算する
- 石の個数は偶奇だけを見る
- SG 値ごとの頻度を持つ
ことで、全体を \(O(N+M)\) で処理します。
アルゴリズム
各 \(A_i\) の偶奇を記録する。
- 奇数なら
par[i] = 1 - 奇数個の石があるマス数
odd_countも数える
- 奇数なら
矢印を隣接リストとして保存する。
マス \(1\) から \(N\) まで順に SG 値を計算する。
- 矢印は常に大きい番号から小さい番号へ向かうので、マス \(u\) を処理するとき、移動先の SG 値はすでに求まっている。
- 移動先の SG 値を集合として見て、その mex を
sg[u]とする。 - 出る矢印がないマスの SG 値は \(0\)。
奇数個の石があるマスだけを見て、初期ニム和
xorsumを計算する。
$\( \text{xorsum} = \bigoplus_{i : A_i \text{ が奇数}} sg[i] \)$
同時に、freq[sg[i]] を数える。
xorsumの値に応じて答えを求める。xorsum == 0のとき
$\( \text{ans} = \text{odd\_count} - \text{freq}[0] \)$
xorsum != 0のときxorsum <= Mなら
$\( \text{ans} = N - \text{freq}[\text{xorsum}] \)$
xorsum > Mなら
$\( \text{ans} = N \)$
計算量
- 時間計算量: \(O(N+M)\)
- 空間計算量: \(O(N+M)\)
SG 値の計算では各矢印を一度ずつ見ます。
mex の計算も、各頂点の出次数に比例する範囲で済むため、全体で \(O(N+M)\) です。
実装のポイント
\(N\) が最大 \(10^6\) と大きいため、高速入力を使っています。
A_iは値そのものではなく偶奇だけをbytearrayに保存しています。mex 計算で毎回配列を初期化すると重いので、
seen配列とstampを使って「今回見た SG 値」を管理しています。SG 値は最大でも \(M\) 以下ですが、複数の SG 値の XOR である
xorsumは \(M\) を超えることがあります。そのため、xorsum > Mの場合を別に扱っています。ソースコード
import sys
def main():
data = sys.stdin.buffer.read() + b' '
idx = 0
def ni():
nonlocal idx
while data[idx] <= 32:
idx += 1
x = 0
while data[idx] > 32:
x = x * 10 + (data[idx] - 48)
idx += 1
return x
N = ni()
M = ni()
par = bytearray(N + 1)
odd_count = 0
for i in range(1, N + 1):
if ni() & 1:
par[i] = 1
odd_count += 1
head = [-1] * (N + 1)
to = [0] * M
nxt = [0] * M
for e in range(M):
u = ni()
v = ni()
to[e] = v
nxt[e] = head[u]
head[u] = e
data = None
sg = [0] * (N + 1)
seen = [0] * (M + 1)
stamp = 0
for u in range(1, N + 1):
e = head[u]
if e != -1:
stamp += 1
while e != -1:
seen[sg[to[e]]] = stamp
e = nxt[e]
g = 0
while seen[g] == stamp:
g += 1
sg[u] = g
freq = [0] * (M + 1)
xorsum = 0
for i in range(1, N + 1):
if par[i]:
g = sg[i]
xorsum ^= g
freq[g] += 1
if xorsum == 0:
ans = odd_count - freq[0]
elif xorsum <= M:
ans = N - freq[xorsum]
else:
ans = N
print(ans)
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: