Pythonでストーンゲームの最大スコアを求めるプログラム（区間DP・メモ化再帰）

問題の概要

いくつかの石が一列に並んでおり、各石には数値が割り当てられています。これらの数値は配列 stoneValue として与えられます。各ラウンドでは、まず Amal が石の列を2つの部分に分割し、続いて Bimal がそれぞれの部分の値（その部分に含まれる全石の合計値）を計算します。そして Bimal は値が大きい方の部分を捨て、Amal のスコアは残った部分の値だけ増加します。両部分の値が等しい場合は、どちらを捨てるかを Amal が自由に決められます。次のラウンドは残った部分から始まり、石が1つだけ残った時点でゲーム終了です。Amal が獲得できるスコアの最大値を求めてください。

入力例とシミュレーション

入力が stoneValue = [7,3,4,5,6,6] の場合、出力は 24 になります。

• 1ラウンド目： Amal は列を [7,3,4] と [5,6,6] に分割します。左の合計は14、右の合計は17なので、Bimal は値の大きい右側を捨て、Amal のスコアは 14 になります。

• 2ラウンド目： 残った [7,3,4] を [7] と [3,4] に分割します。両方の合計は7で等しいので、Amal は左側を捨てることを選び、スコアは 14 + 7 = 21 になります。

• 3ラウンド目： 残った [3,4] を [3] と [4] に分割します。Bimal は値の大きい右側を捨て、Amal のスコアは 21 + 3 = 24 になります。

解法のアプローチ

この問題は「区間の部分和の前計算」と「メモ化再帰（トップダウンDP）」を組み合わせることで効率的に解けます。手順は以下のとおりです。

• 関数 dfs(start, end) を定義します。区間 [start, end] で得られる最大スコアを返します。

• start >= end の場合（石が1つ以下）は、これ以上分割できないため 0 を返します。

• max_score := 0 で初期化します。

• cut を start から end-1 まで動かしながら以下を繰り返します。

  • sum1 := 区間 [start, cut] の部分和

  • sum2 := 区間 [cut+1, end] の部分和

  • sum1 > sum2 のとき：score := sum2 + dfs(cut+1, end)

  • sum1 < sum2 のとき：score := sum1 + dfs(start, cut)

  • 等しいとき：score := sum1 + max(dfs(start, cut), dfs(cut+1, end))

  • max_score := max(score, max_score) ―― この更新は条件分岐の外で、すべての cut に対して必ず行うのが重要なポイントです。特定の分岐内だけで更新すると誤った結果になります。

• max_score を返します。

• 関数 getPartialSum() を定義し、任意の区間 [i, j] の石の合計を partial_sum[i][j] として前計算しておきます。

• メイン処理では、n := stoneValue のサイズ、partial_sum := n × n のゼロ初期化二次元配列を用意し、getPartialSum() を呼び出した後、dfs(0, n-1) を返します。

実装例

以下にPythonでの実装例を示します。再帰による重複計算を避けるため、functools.lru_cache によるメモ化を追加しています。

from functools import lru_cache


def solve(stoneValue):
    n = len(stoneValue)

    # 区間 [i, j] の石の合計を前計算
    partial_sum = [[0] * n for _ in range(n)]
    for i in range(n):
        partial_sum[i][i] = stoneValue[i]
        for j in range(i + 1, n):
            partial_sum[i][j] = partial_sum[i][j - 1] + stoneValue[j]

    @lru_cache(maxsize=None)
    def dfs(start, end):
        if start >= end:
            return 0
        max_score = 0
        for cut in range(start, end):
            sum1 = partial_sum[start][cut]
            sum2 = partial_sum[cut + 1][end]
            if sum1 > sum2:
                score = sum2 + dfs(cut + 1, end)
            elif sum1 < sum2:
                score = sum1 + dfs(start, cut)
            else:
                score = sum1 + max(dfs(start, cut), dfs(cut + 1, end))
            max_score = max(score, max_score)
        return max_score

    return dfs(0, n - 1)


stoneValue = [7, 3, 4, 5, 6, 6]
print(solve(stoneValue))

入力

[7,3,4,5,6,6]

出力

24

計算量について

部分和の前計算に O(n²)、DFSの状態数は O(n²)、各状態で分割位置を最大 O(n) 通り試すため、全体の計算量は O(n³) となります。メモ化によって同じ区間の再計算が不要になるため、素朴な再帰（指数時間）に比べて大幅に高速化できます。