C++で解くストーンゲーム（Stone Game）：区間DPによる解法

問題の概要

AlexとLeeという2人のプレイヤーが、石の山を使ったゲームを行います。山は一列に並んでおり、その数は必ず偶数、各山には piles[i] 個の石が入っています。ゲームの目的は、最終的に相手より多くの石を手にすることです。石の総数は奇数であるため、引き分けは発生しません。Alexが先手となり、2人は交互に手番を進めます。各ターンでプレイヤーは、列の先頭または末尾にある山を丸ごと1つ取らなければなりません。これを山が無くなるまで繰り返し、最後に多くの石を持っていたプレイヤーの勝利です。両者が常に最適な手を選ぶと仮定したとき、「Alexが勝つかどうか」を判定するのがこの問題です。

例えば、入力が [5,3,4,5] の場合、結果は true（出力は 1）になります。Alexは先手のため、最初に選べるのは先頭の5か末尾の5のどちらかだけです。

• 先頭の5を取った場合：列は [3,4,5] になります。ここでLeeが3を取れば盤面は [4,5] となり、Alexは5を取って合計10点で勝利します。Leeが末尾の5を取った場合は盤面が [3,4] となり、Alexは4を取って合計9点で勝てます。

つまり、先頭の5を取ることがAlexにとって勝ちにつながる一手であり、答えは true となります。

解法アプローチ

この問題は区間DP（インターバル・ダイナミックプログラミング）と累積和を組み合わせて効率よく解けます。ここで dp[i][j] は「区間 [i, j] の山が残っている状態で手番のプレイヤーが獲得できる石の最大数」を表します。手順は以下の通りです。

1. n := 配列 piles のサイズとします。
2. n×n の二次元配列 dp と、サイズ n+1 の配列 pre（累積和用）を作成します。
3. i を 0 ～ n−1 でループし、pre[i + 1] := pre[i] + piles[i] として累積和を構築します。
4. 区間長 l を 2 ～ n でループします。
   i := 0、j := l − 1 から始め、j < n の間、i と j を1ずつ増やしながら次の遷移式を計算します：
   dp[i][j] := max( piles[j] + pre[j] − pre[i] − dp[i][j−1]、piles[i] + pre[i+2] − pre[j] + dp[i+1][j] )
5. 最後に dp[0][n−1] が全区間の総和（pre[n]）の半分を超えているか、すなわちコード上の条件 dp[0][n−1] > dp[0][n−1] − pre[n] を満たす場合に true を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector<vector<int>> dp(n, vector<int>(n));
      vector<int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1],
                            piles[i] + pre[i + 2] - pre[j] + dp[i + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

入力

[5,3,4,5]

出力

1

計算量の評価

時間計算量は区間の組み合わせをすべて調べるため O(n²)、空間計算量もDPテーブルと累積和配列の分の O(n²) となります。

補足：数学的な性質

実はこの古典的な設定（山の数が偶数個・総数が奇数）では、先手のAlexが必ず勝つことが証明されています。Alexは初手以降、常に「偶数番目の山のみ」か「奇数番目の山のみ」のどちらか一方を取り続けることを強制できるため、合計の多い方のグループを選択すればよいからです（LeetCode 877「Stone Game」として知られる問題）。とはいえ、山の数が奇数になるなどの一般化されたバリエーションにも対応できるよう、本記事のような区間DPアプローチを理解しておくことは非常に重要です。