C++で解くストーンゲームII：メモ化再帰と動的計画法による最適解法

ストーンゲームIIの問題概要

2人のプレイヤー、AliceとBobが一列に並んだ石の山で対戦します。各山には正の整数の石が入っており、配列 piles[i] として表されます。ゲームの目的は、最終的に最も多くの石を獲得することです。

両者は交互に手番を進め、Aliceが先攻です。初期状態では M = 1 となっています。各プレイヤーの手番では、残っている山のうち先頭から X 個（ただし 1 ≤ X ≤ 2M）を選び、そこにある石をすべて取ることができます。手番の直後には M が max(M, X) に更新されます。石がすべてなくなった時点でゲーム終了です。

例として piles = [2,7,9,4,4] の場合を考えてみましょう。このときの出力は 10 になります。Aliceが最初に1つの山だけ取れば、Bobは2つの山を取り、その後Aliceはさらに2つの山を取れます。この場合、Aliceの獲得数は 2 + 4 + 4 = 10 です。一方、Aliceが最初に2つの山を取ると、Bobが残り3つの山をすべて奪ってしまうため、Aliceは 2 + 7 = 9 個しか得られません。よって、大きい方の 10 が答えとなります。

解法のアプローチ

この問題は、メモ化再帰（Memoization）と動的計画法を組み合わせることで効率的に解けます。まず、インデックス i 以降の石の総数を格納する累積和配列 arr を用意します。「自分の取り分 ＝ 残りの石の総数 − 相手が取る石の数」という関係を利用するのがポイントです。

再帰関数 solve の設計

solve 関数は、配列 arr・現在のインデックス i・パラメータ m・メモ用テーブル dp を引数に取ります。処理の流れは以下のとおりです。

1. i が配列サイズ以上なら 0 を返す（ベースケース）。
2. dp[i][m] が -1 以外（計算済み）なら、その値を返して再計算を省く。
3. i − 1 + 2m ≥ 配列サイズ の場合、残りの山をすべて取り切れるため arr[i] を返す。
4. opponentCanTake を無限大（INT_MAX）で初期化する。
5. x を 1 から 2m まで変化させながら、solve(arr, i + x, max(x, m), dp) の結果の最小値を opponentCanTake に記録する。
6. dp[i][m] ＝ arr[i] − opponentCanTake として、その値を返す。

ここで重要なのは「相手が取れる量を最小化することが、自分の獲得量の最大化につながる」というミニマックス戦略の考え方です。残りの総石数 arr[i] から相手の取得分を差し引けば、自分の最適な取り分が求まります。

メイン処理の構築

1. n を piles のサイズとし、長さ n の配列 arr を作成する。
2. arr[n−1] ＝ piles[n−1] と設定する。
3. i を n−2 から 0 まで逆順に走査し、arr[i] ＝ arr[i+1] ＋ piles[i] で累積和を埋めていく。
4. (n+1) × (n+1) の二次元配列 dp を作成し、すべて -1 で初期化する。
5. solve(arr, 0, 1, dp) の結果を返す。

C++での実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    void printVector(vector <int> v){
        for(int i =0;i<v.size();i++)cout << v[i] << " ";
        cout << endl;
    }
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector <int> arr(n);
        arr[n-1] = piles[n-1];
        for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
        vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
        return solve(arr,0,1,dp);
    }
    int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
        if(i >=arr.size())return 0;
        if(dp[i][m]!=-1)return dp[i][m];
        if(i-1+2*m >=arr.size())return arr[i];
        int opponentCanTake = INT_MAX;
        for(int x =1;x<=2*m;x++){
            opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
        }
        dp[i][m] = arr[i] - opponentCanTake;
        return dp[i][m];
    }
};
main(){
    vector<int> v = {2,7,9,4,4};
    Solution ob;
    cout <<(ob.stoneGameII(v));
}

入力

[2,7,9,4,4]

出力

10

まとめ

ストーンゲームIIは、累積和の前計算とメモ化再帰を組み合わせることで、重複する状態の再計算を避けながら効率的に最適解を導ける、典型的な動的計画法の問題です。「自分の取り分 ＝ 残り全体 − 相手の最小取得分」という視点が理解の鍵となります。