Pythonでストーンゲームの勝敗を判定！Amalが勝てるかチェックするプログラム

2人のプレイヤーAmalとBimalがゲームを行い、Amalが先手です。最初、山にはn個の石が積まれています。各プレイヤーは自分のターンに、山から「平方数（0以外）」個の石を取り除かなければなりません。そして、これ以上手を打てなくなったプレイヤーが負けとなります。nが与えられたとき、Amalがこのゲームに勝てるかどうかを判定しましょう。

例えば、n = 21の場合、答えは True になります。Amalが最初に16個の石を取ると、Bimalは4個取り、最後にAmalが残りの1個を取って勝利できるからです。

解法のアプローチ

この問題は動的計画法（DP）で効率よく解けます。dp[i] を「i個の石が残っているとき、その手番のプレイヤーが勝てるか」を表す真偽値とします。もし「iからある平方数を引いた局面（i − 平方数）で相手が負ける」のであれば、現在の手番のプレイヤーは必ず勝てます。

アルゴリズムの手順

• n以下のすべての平方数をリスト squares に生成します（差分が奇数ずつ増える性質を利用）
• サイズ(n+1)のDPテーブル dp を用意し、dp[0] = False（石が0個なら手番のプレイヤーは負け）と初期化します
• k = 1 から n まで順に処理し、k から平方数を引いた局面 dp[k − 平方数] が False（相手が負ける）になるものが1つでもあれば、dp[k] = True とします
• 最後に dp[n] を返せば、Amal（先手）が勝てるかどうかが分かります

実装例

以下のPythonコードで理解を深めましょう。

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

入力

21

出力

True

このアルゴリズムの時間計算量は O(n√n) 程度であり、nが大きくなっても十分高速に動作します。ゲーム理論の基本的な勝敗判定パターンの一つなので、競技プログラミングでも応用範囲が広い考え方です。