問題
$N$ 個の石の山、山 $i$ には $A_i$ 個。2人が交互に1個以上任意個数を取り、取れなくなったら負け。先手必勝か判定せよ。
制約
$1 \le N \le 10^5$
$1 \le A_i \le 10^9$
入出力例
入力例 1
3
3 5 7出力例 1
First入力例 2
2
4 4出力例 2
Secondヒント (段階的開示)
ヒント1: 方向性
典型的な Nim ゲーム。Grundy 数（XOR の性質）。
ヒント2: アプローチ
全ての山の XOR が 0 かどうかで勝敗が決まる。
ヒント3: 誘導
xor_sum = 0
for a in A:
xor_sum ^= a
print("First" if xor_sum != 0 else "Second")模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N = int(input())
A = list(map(int, input().split()))
xor_sum = 0
for a in A:
xor_sum ^= a
if xor_sum != 0:
print("First")
else:
print("Second")
solve()Step-by-Step 解説
1Nim ゲームの勝敗定理
Sprague-Grundy: 複数の独立したゲームを同時に行う場合、全体の Grundy 数 = 各ゲームの Grundy 数の XOR。
Sprague-Grundy: 複数の独立したゲームを同時に行う場合、全体の Grundy 数 = 各ゲームの Grundy 数の XOR。
2Nim の Grundy 数
山に $k$ 個の石がある Nim の山の Grundy 数は $k$ そのもの。
山に $k$ 個の石がある Nim の山の Grundy 数は $k$ そのもの。
3勝敗判定
Nim 和 ≠ 0 → 先手必勝、Nim 和 = 0 → 後手必勝。
Nim 和 ≠ 0 → 先手必勝、Nim 和 = 0 → 後手必勝。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
XOR を + と混同 | XOR は ^ 演算子 | xor_sum ^= a |
| 0 のとき後手勝ちと混乱 | Nim 和 0 → 後手有利 | if xor_sum != 0: First |
| $N=1$ を分岐 | 定理は $N=1$ でも成立 | 分岐不要 |
次のステップ
- 発展問題: 各山から取れる石の数が $1 \sim K$ に制限された Nim
- Grundy 数を手計算で求めるトレーニング