C++で両端から数字を取り合うゲームの勝者を予測する方法

負でない整数からなるスコア配列が与えられたとします。2人のプレイヤーが交互に配列の両端から数値を1つずつ選んでいきます。最初にプレイヤー1が選択し、次にプレイヤー2、その後再びプレイヤー1という順番で続きます。一度選ばれた数値は、もう一方のプレイヤーが選ぶことはできません。すべてのスコアが選ばれ終わった時点で、より高い合計スコアを獲得したプレイヤーが勝者となります。ここでは、スコア配列が与えられたときに、プレイヤー1が勝利できるかどうかを予測するプログラムをC++で作成します。

問題例

入力が [1, 5, 233, 7] の場合を考えてみましょう。このときの出力は True(真)になります。

まずプレイヤー1が「1」を選んだとします。するとプレイヤー2は「5」と「7」のどちらか一方しか選べません。どちらを選んでも、プレイヤー1は次の手番で「233」を取ることができます。最終的に、プレイヤー1の合計スコアは234(1 + 233)、プレイヤー2の合計スコアは12(5 + 7)となり、プレイヤー1の方が上回ります。したがって、プレイヤー1が勝てるので true を返します。

解法のアプローチ

この問題は区間DP(動的計画法)を用いて効率的に解くことができます。各区間について、先手(プレイヤー1)と後手(プレイヤー2)がそれぞれ獲得できる最大スコアを計算していきます。具体的な手順は以下の通りです。

1. n が 1 の場合:

   • true を返す(残りの数値をプレイヤー1がすべて取るため必ず勝つ)

2. サイズ n × n の3つの二次元配列 player1、player2、sum を定義し、player1 と player2 の全要素を -1(未計算)で初期化します。

3. 各区間 [i, j] の合計値 sum[i][j] を累積和として事前に計算しておきます。

4. 区間の長さ length を 1 から n まで順に伸ばしながら、各開始位置 i に対して以下を計算します。

   • end := i + length − 1(区間の終端位置)

   • i + 1 ≤ end の場合:

     • player1[i][end] = max(arr[i] + player2[i+1][end], arr[end] + player2[i][end−1])
       ※player2 の値が -1(未計算)の場合は 0 として扱います。

   • それ以外(区間の長さが1)の場合:

     • player1[i][end] := arr[i]

   • player2[i][end] := sum[i][end] − player1[i][end]
     (後手のスコアは、区間全体の合計から先手の取得分を引いた値になります)

5. 最後に、player1[0][n−1] ≥ player2[0][n−1] であれば true、そうでなければ false を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli solve(vector <int> arr, lli n){
      if (n == 1)
         return true;
      lli player1[n][n], player2[n][n], sum[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            player1[i][j] = -1;
            player2[i][j] = -1;
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
            if (i == j) {
               sum[i][j] = arr[i];
            }
            else {
               sum[i][j] = arr[j] + sum[i][j - 1];
            }
         }
      }
      for (int length = 1; length <= n; length++) {
         for (int i = 0; i + length - 1 < n; i++) {
            lli end = i + length - 1;
            if (i + 1 <= end)
               player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ? 0 : player2[i][end - 1]));
            else
               player1[i][end] = arr[i];
            player2[i][end] = sum[i][end] - player1[i][end];
         }
      }
      return player1[0][n - 1] >= player2[0][n - 1];
   }
   bool PredictTheWinner(vector<int>& nums) {
      return solve(nums, nums.size());
   }
};
int main(){
   Solution ob;
   vector<int> v = {1, 5, 233, 7};
   cout << (ob.PredictTheWinner(v));
}

入力

{1, 5, 233, 7}

出力

1

出力が「1」になっているのは、結果が true(プレイヤー1の勝利)であることを意味しています。このように区間DPを活用することで、O(n²) の計算量で先手が勝利できるかどうかを正確に判定できます。