C++で解く「New 21 Game」問題：動的計画法による確率計算

カードゲーム「21」をベースにした、次のようなゲームを考えてみましょう。プレイヤーのリマは0点からスタートし、所持点がK点未満である間、数字を引き続けます。各ターンでは、区間 [1, W] に含まれる整数の中からランダムに1つを選んで加点します（Wは与えられた整数）。各抽選は互いに独立しており、すべての出目は等しい確率で現れるものとします。リマは合計がK点以上になった時点で数字を引くのをやめます。このとき、彼女の最終的な得点がN点以下になる確率を求めてください。

例として、N = 6、K = 1、W = 10 の場合を考えます。K = 1 なので、リマは最初に1枚カードを引いた時点で必ず1点以上となり、その場でゲームが終了します。10通りある出目のうち、1〜6の6通りが N = 6 以下に該当するため、答えは 0.6 となります。

解法のアプローチ

この問題は動的計画法（DP）とスライディングウィンドウ（累積和）を組み合わせることで、O(N) の計算量で効率的に解くことができます。ここでは、dp[i] を「最終的にちょうど i 点でゲームが終わる確率」と定義します。手順は以下の通りです。

• K = 0 の場合、または N ≥ K + W の場合は、どのように数字を引いても必ず条件を満たすため、1.0 を返します。
• サイズ N + 1 の配列 dp を用意し、dp[0] = 1 で初期化します。
• wsum = 1.0（直近 W 個の dp 値の和）、ret = 0.0（答えの累積値）とします。
• i を 1 から N まで順に処理します。
  • dp[i] = wsum / W とします。
  • i < K の場合は wsum += dp[i]（まだ数字を引き続ける可能性があるため）、それ以外の場合は ret += dp[i]（その時点で終了し、かつ N 以下であれば答えに加算）。
  • i − W ≥ 0 の場合は wsum -= dp[i − W]（ウィンドウの範囲外となった古い値を除外）。
• 最後に ret を返します。

dp[i] を毎回 W 個分の総和から直接計算すると O(N × W) かかりますが、wsum を少しずつ更新しながら管理することで、計算量を O(N) に抑えられるのがこの解法のポイントです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double new21Game(int N, int K, int W) {
      if(K == 0 || N >= K + W) return 1.0;
      vector<double> dp(N + 1);
      dp[0] = 1;
      double Wsum = 1.0;
      double ret = 0.0;
      for(int i = 1; i <= N; i++){
         dp[i] = Wsum / W;
         if(i < K){
            Wsum += dp[i];
         }else ret += dp[i];
         if(i - W >= 0) Wsum -= dp[i - W];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.new21Game(6, 1, 10));
}

入力

6
1
10

出力

0.6