足跡-sokuseki-

りかの日進月歩の記録

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

競技プログラミング AtCoder

C - Cheating Nim

問題概要

2人でNimをする。
はじめに $N$ 個の山があり、 $i$ 番目の山には石が $a_i$ 個ある。
ゲームが始まる前に、それぞれの山から石を0個または1個取り除く。
後手が必ず勝つために取り除く石の数の最小値を求めよ。

制約

$1 \le N \le 10^5$
$2 \le a_i \le 10^9$

解法

Nimで後手が勝つためには、すべての山の石の個数のxorが0でなければならない。
よって、この問題は、「それぞれの山から石を0個または1個取り除いて全体のxorを0にするときの取り除く最小の個数を求める」問題に帰着する。

はじめ、すべての山の石の個数のxorが $x$ で、石が $a_i$ 個ある山から石を1個取り除いた時、全体のxorは $x$ xor $a_i$ xor $(a_i - 1)$ になる。
ここで、 $a_i$ xor $(a_i - 1)$ は $2^k - 1$ と表せるので、全体のxorは $x$ xor $( 2^k - 1 )$ となる。
つまり、この操作において、全体のxorは下位 $k-1$ ビットのみが変更されることがわかる。

よって、 $x$ の上位ビットから順番に見ていき、 $x$ の $k$ ビット目が1だったら、 $a_i$ xor $(a_i - 1)$ が $2^{k+1} - 1$ となる山から石を1個取り除けばよい。

最終的に $x$ が0になれば取り除いた個数を出力し、 $x$ が0にならなければ-1を出力する。

$a_i \le 10^9$ より $x$ は高々32ビット程度なので、各ビットについて石を取り除く山を $O(N)$ で調べても十分間に合う。

Submission #3024566 - CODE FESTIVAL 2016 Grand Final(Parallel)