Pythonでストーンゲームのスコア差を求めるプログラム（動的計画法で解説）

問題概要

左から i 番目の石の価値が stones[i] で表される配列 stones があるとします。Amal（アマル）と Bimal（ビマル）という2人のプレイヤーが、この石を使って交互にターン制のゲームを行います。石は合計 n 個が一列に並んでおり、必ず Amal が先手です。各プレイヤーは自分のターンに、列の左端または右端の石を1つ取り除き、残った石の価値の合計を得点として獲得します。最終的に高いスコアを取った方が勝者です。

ここで Bimal は、このゲームでは自分が常に負けてしまうことに気づき、スコアの差をできるだけ小さくする戦略を選ぶことにしました。一方、Amal はスコアの差を最大化することを目指します。両者が最適なプレイをしたとき、Amal と Bimal のスコアの差を求めるのがこの問題です。

具体例で確認

入力が stones = [6, 4, 2, 5, 3] の場合、出力は 8 になります。実際の手順を追ってみましょう。

• Amal が右端の 3 を取り、残り [6, 4, 2, 5] の合計 17 点を獲得（Amal: 17 / Bimal: 0）
• Bimal が左端の 6 を取り、残り [4, 2, 5] の合計 11 点を獲得（Amal: 17 / Bimal: 11）
• Amal が左端の 4 を取り、残り [2, 5] の合計 7 点を獲得（Amal: 24 / Bimal: 11）
• Bimal が左端の 2 を取り、残り [5] の合計 5 点を獲得（Amal: 24 / Bimal: 16）
• Amal が最後の 5 を取り、残りの石がないため 0 点（Amal: 24 / Bimal: 16）

最終的なスコアは Amal が 24 点、Bimal が 16 点となり、その差は 24 − 16 = 8 です。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解けます。dp[j] には「対象となる区間で最適にプレイしたときのスコア差」が格納されます。手順は以下の通りです。

• n を石の総数とする
• サイズ n の配列 dp を作成し、すべて 0 で初期化する
• i を n−1 から 0 まで 1 ずつ減らしながら繰り返す：
  • v := stones[i]
  • run_sum := 0
  • j を i+1 から n−1 まで繰り返す：
    • new_run := run_sum + stones[j]
    • dp[j] := max(new_run − dp[j], run_sum + v − dp[j−1])
    • run_sum := new_run
• dp[n−1] を返す

動的計画法のポイント

dp[j] は「現在の手番プレイヤーが相手に対して付けられる最大のスコア差」を表します。石を左端から取る場合と右端から取る場合のそれぞれについて、「今回獲得できる得点」から「その後の局面での相手の優位性（dp値）」を差し引いた値を比較し、大きい方を採用します。これにより、両者が最適にプレイした際の最終的なスコア差を O(n²) の計算量で求められます。

実装例

以下は Python による実装です。

def solve(stones):
    n = len(stones)
    dp = [0] * n

    for i in range(n - 1, -1, -1):
        v = stones[i]
        run_sum = 0

        for j in range(i + 1, n):
            new_run = run_sum + stones[j]
            dp[j] = max(new_run - dp[j], run_sum + v - dp[j - 1])
            run_sum = new_run
    return dp[n - 1]

stones = [6, 4, 2, 5, 3]
print(solve(stones))

入力

[6,4,2,5,3]

出力

8