ARC 201-300/ARC208A - Bitwise OR Game - 競技プログラミング用 知識集積所

---

問題

ARC208A

必要知識

簡単な内容は省略

• 考察問題
• Nim※

考え方

考察問題。

OR値不変の制約がない通常のNim※は

• 何をやっても石の個数のXOR値が変わる
• XOR値が0でない状態で自分の番になったら、必ずXOR値を0にして返せる
• ゲームが終了するときに、必ずXOR値が0になっている

の3つから、自分の手番で常にOR値が0になるようにすれば必勝である。

今回のゲームは、1つめの条件は全く同じ

• 何をやっても石の個数のXOR値が変わる

が成り立つ。

次に3つめの条件だが、今回は「OR値の各ビットに対応するものが1つずつしか残っていない」という状態になったら終了なので、

• ゲームが終了するときに、必ずXOR値がOR値と等しくなっている

という形になる。

あとは、

• XOR値がOR値と等しくない状態で自分の番になったら、必ずXOR値をOR値と等しくして返せる

が成り立てば、必勝法が見える。
これは、

1. XOR値がOR値と等しくない最高位のビットを探し、そのビットが立っている山を選ぶ
   • そのような山は、OR値不変の条件から少なくとも1つあり、またXOR値のそのビットが0であることから偶数個ある、つまり少なくとも2つあることがわかる
2. その山を完全に取り除いたときにXOR値がいくつになるか求める
3. そのXOR値とOR値のXORを取る
4. 選んだ山の石の個数を、求めた値に変更する
   • 注目するビットより上は不変で、注目ビットが1から0になるので、元の石の個数よりは絶対少ない個数になるはずである

という手順で実現可能。

ということで、このゲームの必勝法は「自分の手番で常にXOR値がOR値と等しくなるようにする」である。
つまり、最初から等しい場合は後手のBobが勝ち、そうでない場合は先手のAliceの勝ちである。

解答例

解答例

注意点

別解