bouzuya.hatenablog.com

ぼうずやのにっき

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(N2) で解けない。

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


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

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


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


今日のコミット。