ゼロ削除ニム―ARC218B問題の誤読でできた問題
ARC218のB問題で盛大な誤読をかまして全くの別問題を解いてしまったので供養します．元の問題の答えには言及しないので，知りたい方は自分で解くか 解説 を見てください．
元の問題
リンク
問題概要
$n$個の非負整数の列$A_{1},A_{2},\cdots ,A_{n}$が与えられる．二人のプレイヤーで次のようなゲームを行う．
- 数列の中で最小の非負整数を$m$とする．
- $m\gt0$のとき，$1\le x \le m$をみたす$x$を選び，数列内のすべての数から$x$を引く．
- $m=0$のとき，数列の中にある$0$のうち，$1$個以上を削除する．
どちらも最善手を取ったとき，どちらが勝つか判定せよ．
誤読でできた問題
問題概要
$n$個の非負整数の列$A_{1},A_{2},\cdots ,A_{n}$が与えられる．二人のプレイヤーで次のようなゲームを行う．
- 数列の中で最小の非負整数を$m$とする．
- $m\gt0$のとき，$1\le x \le n$をみたす$x$を選び，$A_x$から$1$以上の数を引く．
- $m=0$のとき，数列の中にある$0$を$1$個削除する．
どちらも最善手を取ったとき，どちらが勝つか判定せよ．
解説
明らかに数列内の任意の要素について独立なので，Sprague-Grundy数を使える．
以下、数列の要素自体が存在しない($0$ではない)場合を$null$とする．
数列の要素が一つだけの場合について考えると，$(null)$のときSprague-Grundy数は$0$，$(0)$のとき$1$，$(1)$のとき$0$，$(m)(m\geq2)$のとき$m$となることが分かる．
終了局面は明らかに$(null)$で，このときSprague-Grundy数は$0$．
局面$(0)$からは局面$(null)$に遷移できるので，Sprague-Grundy数は$1$．
局面$(1)$からは局面$(0)$に遷移できるので，Sprague-Grundy数は$0$．
局面$(2)$からは局面$(0)$と局面$(1)$に遷移できるので，Sprague-Grundy数は$2$．
$(m)$のSprague-Grundy数が$m$であるとき，局面$(m+1)$からは局面$(m)$と局面$(m)$から遷移できるすべての局面に遷移できる．ここで，仮定より局面$(0),(1),\cdots ,(m-1)$のSprague-Grundy数の集合には整数$0,1,\cdots ,m-1$が過不足なく含まれる．したがって，局面$(m+1)$から遷移できる局面のSprague-Grundy数の集合には整数$0,1,\cdots ,m-1,m$が含まれ，それ以外の数は含まれないので、局面$(m+1)$のSprague-Grundy数は$m+1$．
$3$番目と$4$番目の結果より，$m\geq2$のとき局面$(m)$のSprague-Grundy数は$m$．
以上より，Sprague-Grundy数が任意の局面に対して求まった．
コード
n = int(input()) #nを受け取る
a = list(map(int, input().split())) #aを受け取る
Sprague = 0
for aa in a:
#以下Sprague-Grandy数を求める
if aa == 0:
Grundy = 1
elif aa == 1:
Grundy = 0
else:
Grundy = aa
#ニム和をとる
Sprague ^= Grundy
#必勝判定
if Sprague == 0:
print("Second")
else:
print("First")
終わりに
改めてSprague-Grandy数の威力を思い知った。しかし単純であまり面白くない結果だったので、もうちょっとひねった問題を考えたい。
