Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 131 C 問題 Zero XOR

AtCoder ARC ARC131 C問題 600 pts

問題

提出解答

問題の概要

重複がない正の整数の列 $A=(A_i)_{i=1}^N$ があり, 以下のゲームを行う. ただし, 正の整数の列 $B$ に対して, $\bigoplus B$ で, $B$ の全ての要素における XOR とする.

先手から次の行動を交互に行う.
- $A$ から1要素取り除く. そのとき, $\bigoplus A=0$ ならば, その人の勝ちでゲームを終了する.

後手が勝利のために最善に行動する場合, 先手は勝てるか?

制約

$1 \leq N \leq 4 \times 10^5$
$1 \leq A_i \leq 10^9$
$i \neq j \Rightarrow A_i \neq A_j$
$\bigoplus A \neq 0$

解法

この問題の本質は, 以下の事実である.

$N$ が奇数ならば, どんな $A$ に対しても, 先手必勝である.

$N=1$ のとき: 最後の1要素を取ることにより, $A$ は空列になり, $\bigoplus A=0$ になる.
のときに成立するとする. のとき,
- 直接勝てる手が存在する場合, このような手を選択すれば勝利することができる.
- 直接勝てる手が存在しない場合, どのような手を選択したとしても, 後手が直後には勝てないということを示す. 背理法で示す. $A_p$ を消すことを選択するとする. このとき, 背理法の仮定から, $A_q$ を消すことによって勝つことができるとする. このとき, $\bigoplus_{i=1}^N A_i=A_p \oplus A_q$ である. このとき, XOR は群で, $A$ の各項は互いに異なることから, このような $q$ は一意に定まる. よって, この $q$ のことを $f(p)$ と書くことにする. すると, $f(q)=f(f(p))=p$ が成り立つことに注意する. そして, $p \neq f(p)$ であるから, $\{1,2, \dots, N\}$ は $\{p,f(p)\}$ によって, $N/2$ 個の直和に分解される. しかし, これは $N$ が奇数であることに矛盾する. よって, うまいこと手を選ぶことによって, 後手が直後に勝つことはできず, $N-2$ の場合に帰着される. よって, 帰納法の仮定から, 先手が勝てる.

よって, この事実から, 以下のようにして判定できる.

$N$ が奇数の場合: 必ず勝てる.
$N$ が偶数の場合: 最初の手で勝てない場合, 後手に上の事実を当てはめることにより, 勝てないことが確定してしまう. つまり, $\displaystyle \bigoplus_{\substack{1 \leq j \leq N \\ j \neq i}} A_i=0$ となる $i$ が存在するかを判定する. なお, これは $\displaystyle \bigoplus_{j=1}^N A_j=A_i$ となる $i$ が存在することと同値である.