Pythonで先攻プレイヤーが他のプレイヤーより多くのキャンディーを獲得できるか判定するプログラム

「candies」という数値のリストがあり、2人のプレイヤーがより多くのキャンディーを集める競争をしているとします。このゲームはターン制で行われ、プレイヤー1が先攻です。各ターンで、プレイヤーはリストの先頭または末尾のどちらかからキャンディーを1つ取ることができます。ここでの課題は、プレイヤー1が相手よりも多くのキャンディーを集められるかどうかを判定することです。

問題の例

例えば、入力が candies = [1, 4, 3, 8] の場合、出力は True になります。なぜなら、プレイヤー1は初手で末尾の8個のキャンディーを取ることができ、その後、相手が先頭の1か3のどちらを選んでも、残りのキャンディーを取ることで確実に勝利できるからです。

解決のアプローチ

この問題は、ミニマックス法（ゲーム理論）の考え方を使って解くことができます。ポイントは、「自分のスコア」と「相手のスコア」の差分に着目することです。各ターンで自分が取ったキャンディーの数はプラス、相手が次の手番で取れるキャンディーの数はマイナスとして扱うことで、再帰的に最適な戦略を評価できます。

具体的には、以下の手順で進めます。

• N := candies のサイズ（要素数）とする

• 関数 difference(left, right) を定義する。これは区間 [left, right] における「先手と後手の獲得数の差」を返す

• left が right と等しい場合（キャンディーが1個だけ残っている場合）は、candies[left] を返す

• それ以外の場合は、次の2つの選択肢のうち大きい方を返す：
  candies[left] − difference(left + 1, right)（先頭を取った場合）
  candies[right] − difference(left, right − 1)（末尾を取った場合）

• メイン処理では、difference(0, N − 1) > 0 であれば True を、そうでなければ False を返す

difference() が正の値を返すということは、両者が最適な戦略を取ったときに先攻のプレイヤー1が相手より多くのキャンディーを獲得できることを意味します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
   def solve(self, candies):
      N = len(candies)
      def difference(left, right):
         nonlocal candies
         if left == right:
            return candies[left]
         return max(candies[left] − difference(left + 1, right),
                   candies[right] − difference(left, right − 1))
      return difference(0, N − 1) > 0

ob = Solution()
candies = [1, 4, 3, 8]
print(ob.solve(candies))

入力

[1, 4, 3, 8]

出力

True

計算量について

この実装の時間計算量は O(2^N) となります。これは、各ステップで2つの選択肢（先頭を取るか末尾を取るか）が生じるためです。ただし、メモ化（memoization）を導入して一度計算した (left, right) の組み合わせの結果をキャッシュすれば、計算量を O(N²) まで削減できます。また、空間計算量も再帰呼び出しの深さに応じて O(N) 必要となります。

このように、交互手番のゲームでは「差分」に注目したミニマックス的な再帰が非常に有効です。同様のパターンは、カードゲームや石取りゲームなど、さまざまな最適戦略問題に応用できます。