Pythonでキャンディーゲームの勝敗を判定！プレイヤー1が最大スコアを獲得できるかチェックする方法

2人のプレイヤーがゲームを行う状況を考えてみましょう。一列に並んだ複数のキャンディーがあり、プレイヤー1には各キャンディーの点数を表す数値リスト nums が与えられます。各プレイヤーのターンでは、列の先頭から1個・2個・3個のいずれかの数だけキャンディーを取り除き、その合計点数を自分のスコアに加算します。すべてのキャンディーがなくなった時点でゲームは終了し、より高いスコアを獲得したプレイヤーが勝者となります。ここでは、プレイヤー1がこのゲームに勝てるかどうかを判定する方法を解説します。

たとえば、入力が nums = [1, 1, 2, 3, 50] の場合、出力は True になります。プレイヤー1が最初にキャンディーを1個だけ取ると、相手プレイヤーは必ず1〜3個のキャンディーを取ることになります。その結果、どのような展開になってもプレイヤー1が50点のキャンディーを確保できるためです。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• n := nums のサイズ
• table := 0が3つ格納された配列
• i を n−1 から 0 まで1ずつ減らしながら以下を繰り返す：
  • profit := −inf（負の無限大）
  • sum_val := 0
  • j を i から min(i + 3, n) まで繰り返す：
    • sum_val := sum_val + nums[j]
    • profit := profit と (sum_val − table[j − i]) のうち大きい方
  • table := [profit, table[0], table[1]] という3要素のリストに更新
• table[0] > 0 なら true を返し、それ以外は false を返す

実装例

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

import math
class Solution:
    def solve(self, nums):
        n = len(nums)
        table = [0, 0, 0]
        for i in range(n - 1, -1, -1):
            profit = -math.inf
            sum_val = 0
            for j in range(i, min(i + 3, n)):
                sum_val += nums[j]
                profit = max(profit, sum_val - table[j - i])
            table[:] = [profit, table[0], table[1]]
        return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))

入力

[1, 1, 2, 3, 50]

出力

True

アルゴリズムの仕組み

このソリューションは動的計画法（DP）を活用しています。table 配列は直近3ステップ分の「現在のプレイヤーと相手のスコア差」を保持しており、各位置 i において、1個・2個・3個のキャンディーを取るそれぞれの選択肢について「自分が獲得する合計点数から、その後相手が稼げる最大の差額を引いた値」を計算し、最も有利な選択を profit として記録します。最終的に table[0] が正であれば、先手のプレイヤー1が相手より高いスコアを確保できる、つまり勝利できることを意味します。