ARC131C Zero XOR - geam1113’s diary

解説を見てAC

公式解説に詳しく書かれていますが、自分用にメモしておきます。

・Nが奇数なら先手必勝

・Nが偶数なら、1個取って0にできれば先手必勝、そうでなければ後手必勝

公式解説と少し違いますが、この方が自分にとって直感的でした。やっていることは同じです。

$S=A_1\ XOR\ A_2\ XOR\ \cdots \ XOR\ A_N$
とします。

$x\ XOR\ x=0$

なので、各iについて、

$S\ XOR\ A_i$

を計算すると、 $A_i$ の影響を無くすことができるので、これが0になるか判定すれば良いです。

公式解説に追加して自分の理解した部分も含めて記載しておきます。

まず、以下が言えます。

・自分があるクッキーを食べ、相手が次のターンに勝てる場合、相手が食べるべき整数は一意に定まる。

全体のXORでビットが1のところは、そのビットが1であるクッキーが奇数個存在しており、0のところは偶数個存在していることになります。

例

100101 全体のXORの2進数

322501 各ビットが1であるクッキーの個数

この時、全体のXORのi番目が1である場所(例の場合5,2,0番目のビット)のみが1であるようなクッキーを食べて個数を偶数にする必要があります。

例

100101 全体のXORの2進数

322501 各ビットが1であるクッキーの個数

↓2進数で100101のクッキーを食べる

000000 全体のXORの2進数

222400 各ビットが1であるクッキーの個数

このように、全体のXOR、またはビットが1であるクッキーの個数の偶奇によって、食べるべき整数が一意に定まります。

これを踏まえ、2手先に相手が勝てない理由を示します。

2手先に相手が勝つと仮定します。

全体のXOR、またはビット1の個数の偶奇はとった順番に依存しないので、

・ $A_i \rightarrow A_j$ の順で食べて0になるなら、 $A_j \rightarrow A_i$ の順で食べても0になる

ことがわかり、これをペアと呼びます。

今回、ペアは一意に定まることが言えます。

仮に、 $A_i$ を食べてから $A_j$ を食べても、 $A_k$ を食べても0になるとしたら、それは $A_j=A_k$ の時だけです。問題文に整数は全て異なるという条件があるので、等しくなることはあり得ず、ペアが一意となることが言えました。

相手が次のターンで勝てる場合、自分のどのような行動に対しても相手が勝てる手段があるはずです。

今回の場合、自分がどのクッキーを食べても、そのクッキーに対するペアが一意に存在し、ペアのもう一方を相手が食べることで勝てるような状況になっているはずです。

しかし、残り個数が奇数なので、ペアから外れるものが存在し、それを自分が取れば相手が勝つことはなくなります。

以上より、仮定に反するため、2手先に相手が勝つことはありえません。