C++で解く「ストーンゲームIII」― 動的計画法による最適戦略の実装

問題の概要

AmalとBimalが石を使ったゲームを行います。複数の石が一列に並んでおり、それぞれの石には配列 stoneValue で与えられる数値が割り当てられています。

二人は交互に手番を持ち、Amalが先攻です。各プレイヤーの手番では、列の先頭に残っている石から1個・2個・3個のいずれかを取ることができます。

各プレイヤーのスコアは「取った石の値の合計」で、初期値は0です。ゲームの目的は最も高いスコアで終えることで、スコアの高い方が勝者となります。同点になる場合もあります。ゲームはすべての石がなくなるまで続きます。

ここでは、両者が常に最適な手を選ぶものと仮定します。Amalが勝てば "Amal"、Bimalが勝てば "Bimal"、同点なら "Tie" を返すのが求める出力です。

例えば、入力が values = [1,2,3,7] の場合、出力は Bimal になります。Amalには勝ち筋が存在しないためです。Amalの最善手は3個の石を取ることで、このときスコアは6になります。その後Bimalが値7の石を取るため、Bimalの勝利が確定します。

解法のアプローチ（動的計画法）

この問題は動的計画法（DP）を用いて効率的に解けます。dp[i] は「位置 i から手番が始まったプレイヤーが、以降のゲームで獲得できる最大スコア」を表します。手順は以下の通りです。

• サイズ n + 10 の配列 dp と sum を用意します。
• i = 0 ～ n-1 について、dp[i] を -(10⁹) で初期化します。
• suffix sum を構築します。まず sum[n-1] = v[n-1] とし、i = n-2 から 0 まで逆順に sum[i] = sum[i+1] + v[i] を計算します。sum[i] は「位置 i 以降の石の値の総和」です。
• i = n-1 から 0 まで逆順にループし、各 i について k = i+1 ～ min(i+3, n) の範囲で dp[i] = max(dp[i], sum[i] - dp[k]) を更新します。自分が石を k-i 個取ると相手の手番は位置 k に移るため、「全体の残り sum[i] から相手の獲得分 dp[k] を引いた値」が自分のスコアになります。
• total = sum[0]、x = dp[0]（先手の最大スコア）、y = total - x（後手のスコア）とします。
• x > y なら "Amal"、x == y なら "Tie"、それ以外なら "Bimal" を返します。

この手法により、全探索せずとも両者が最適にプレイした場合の結果を正確に求められます。計算量は時間・空間ともに O(n) です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string stoneGameIII(vector<int>& v) {
        int n = v.size();
        vector<int> dp(n + 10);
        vector<int> sum(n + 10);
        for(int i = 0; i < n; i++) dp[i] = -1e9;
        sum[n - 1] = v[n - 1];
        for(int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + v[i];
        for(int i = n - 1; i >= 0; i--){
            for(int k = i + 1; k <= i + 3 && k <= n; k++){
                dp[i] = max(dp[i], sum[i] - dp[k]);
            }
        }
        int total = sum[0];
        int x = dp[0];
        int y = total - x;
        return x > y ? "Amal" : x == y ? "Tie" : "Bimal";
    }
};
int main(){
    Solution ob;
    vector<int> v = {1,2,3,7};
    cout << (ob.stoneGameIII(v));
}

入力

{1,2,3,7}

出力

Bimal