Pythonで先手が必ず勝てる初手の選び方の数を求めるプログラム

問題の概要

アマルとビマルがゲームをしているとしましょう。2人のもとには n 個の容器があり、それぞれに1個以上のチョコレートが入っています。容器には 1 から N までの番号が付けられており、i 番目の容器には count[i] 個のチョコレートが入っています。

ゲームの進行は以下の通りです。

• 先手のプレイヤーが1つの容器を選び、そこから1個以上のチョコレートを取り除きます。
• 次に後手のプレイヤーが空でない容器を選び、そこから1個以上のチョコレートを取り除きます。
• これを交互に繰り返し、チョコレートを1個も取れなくなったプレイヤーが負けとなります。

アマルが先手であるとき、その後必ず勝てるような初手の選び方が何通りあるかを求めるのがこの問題です。

例えば、入力が count = [2, 3] の場合、出力は 1 になります。初期状態では容器の中身は [2, 3] であり、ゲームは次のように進行します。

• アマルが2番目の容器からチョコレートを1個取る → [2, 2]
• ビマルが1番目の容器からチョコレートを1個取る → [1, 2]
• アマルが2番目の容器からチョコレートを1個取る → [1, 1]
• ビマルが1番目の容器からチョコレートを1個取る → [0, 1]

この状態でビマルは唯一残った容器からしか取れず、最終的にアマルが勝利します。

解き方：XORを用いたNimゲームの戦略

この問題は古典的な「Nim（ニム）」と呼ばれるゲーム理論の問題であり、XOR（排他的論理和）を使うことで効率的に解けます。すべての容器のチョコレート数のXOR（Nim和）が 0 以外であれば先手必勝、0 であれば後手必勝という重要な性質があります。

具体的な手順は以下の通りです。

• tmp := 0 と初期化する
• count 内の各要素 c に対して、tmp := tmp XOR c を計算する
• tmp が 0 の場合、どのような初手を打っても勝てないため 0 を返す
• そうでない場合：
  • moves := 0 と初期化する
  • 各 c に対して、(tmp XOR c) < c が成り立つなら moves に 1 を加算する
  • moves を返す

(tmp XOR c) < c が成り立つということは、「c 個入っている容器から (c − (tmp XOR c)) 個取ることで、全体のNim和を 0 にできる」ことを意味します。Nim和を 0 にできれば、相手がどの手を打っても再び非ゼロに戻るため、最終的に自分が必ず勝てるのです。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(count):
    tmp = 0
    for c in count:
        tmp ^= c

    if not tmp:
        return 0
    else:
        moves = 0
        for c in count:
            moves += (tmp^c) < c
        return moves

count = [2, 3]
print(solve(count))

入力

[2, 3]

出力

1