C++の新しい21ゲーム

リマが次のゲームをプレイするとします。これは、カードゲーム「21」に大まかに基づいています。したがって、リマは0ポイントから始めて、Kポイント未満の間に数字を描きます。さて、各ドローの間に、彼女は範囲[1、W]からランダムに整数のポイントを獲得します。ここでWは与えられ、それは整数です。現在、各抽選は独立しており、結果は同じ確率になります。リマは、K以上のポイントを獲得すると、数字の描画を停止します。彼女のポイントがN以下である確率を見つける必要がありますか？

したがって、N =6、Kが1、Wが10の場合、リマは1枚のカードを取得して停止するため、答えは0.6になります。10の確率のうち6で、彼女はN=6ポイント以下です。

これを解決するには、次の手順に従います-

• kが0、またはN> =K + Wの場合、1を返します
• サイズN+1の配列dpを作成し、dp [0]：=1を設定します
• set wsum：=1.0、ret：=0.0
• 1からNの範囲のiの場合
  • dp [i]：=wsum / W
  • i
  • i – W> =0の場合、wsum：=wsum – dp [i --W]
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#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