2022-01-08 ARC131 C - Zero XOR を解いた

ARC131 C - Zero XOR を解いた。

https://atcoder.jp/contests/arc131/tasks/arc131_c

最後の一個を取り除くか XOR が 0 なら勝ち。後ろから考える。自分の手番で…… 残り 1 個なら勝ち。残り 2 個なら負け。残り 3 個なら勝ち。残り 4 個なら XOR が 0 になれば勝ち、そうでなければ負け。残り 5 個なら任意の 2 個を選択した後に XOR が 0 にならなければ勝ち、そうでなければ負け。

任意の 2 個を選択した後に XOR が 0 にならなければを愚直にやると O(N^2) で解けない。

解説によると偶数個取り除いて奇数個で XOR は 0 にならないことが証明できるので奇数は必勝、偶数なら XOR が 0 にできるなら勝ちということらしい。惜しい。

ABC234 に参加した。 E まで解いて -17 。

https://atcoder.jp/users/bouzuya/history/share/abc234

スーパーマリオオデッセイ雪の国をクリアした。

今日のコミット。