CODE FESTIVAL 2016 Grand Final C - Cheating Nim
解法
まず, Nimなので与えられた数列のXOR和を考えます.
Nimについておさらいしておくと,
- 山のXOR和が0のとき, 後手必勝
- 山のXOR和が0でないとき, 先手必勝
です. 山, 石が0のとき負けのこと, XOR和が0でないときは必ずXOR0の状態に遷移できること, XOR0の状態からはXOR0の状態に遷移できないことを示すことで導かれます.
各山から一個石が取り除けることについて考えます.
具体的に11(=00001011(2進数))個あるものを考えると, 選択肢としては
- 何もしない(11個=00001011(2)のまま)
- 1つだけ取り除く(10個=00001010(2)になる)
の2つの操作ができます.
ここで1つ取り除いたとき, XOR和をとり直すと, 元のXOR和の0ビット目(0-indexed)が反転したものが得られます.
11でなく, 16でこれを試すと,
- 何もしない(16個=00010000(2)のまま)
- 1つだけ取り除く(15個=00001111(2)になる)
これで上と同じようにXORを和をとり直すと, 元のXOR和の0~4ビット目までが反転したものが得られます.
これで法則性が見えました. それぞれの山について, 1つ取り除いたときに最後に1が立つビットより下位のビットをすべて反転させることができます.
アルゴリズムを考えます.
この問題の目的は, XOR和を0にしてやることです. そこで, まず初期のXOR和を計算します.
それぞれのについて, 1が立っている最も下位のビットを記録します.
XOR和のビットを上位から見て, 1が立っているビットがあれば, そこのビット以下を反転させる要素が存在するかどうか調べ, 存在すればそのビット以下をすべて反転させ, カウントを加算します.
ここで, 反転させることができない場合, これ以降どのビットを反転させてもそのビットを0にすることはできないため, -1を出力します.
無事XORを0にすることができれば, カウントを出力します. 上記のアルゴリズムから, このカウントは32より小さいことが示せます.
感想
石を一つ取り除いたときのXOR和の動きに気づいた後は, 蟻本の牛を回転させる問題が参考になります(少なくとも必ず行わなければならない操作を最も損なく行う方法).
