837. New 21 Game
という問題があり、過去最高に意味がわからなかったのですが、やっと理解できたのブログにすることにしました。
問題
問題は以下の通り
Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets k or more points.
Return the probability that Alice has n or fewer points.
Answers within 10-5 of the actual answer are considered accepted.
Example 1:
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
Constraints:
0 <= k <= n <= 104
1 <= maxPts <= 104
引用：https://leetcode.com/problems/new-21-game/description/
アリスという人が１からmaxPtsまであるカードを引いて、合計がKになったらカードをひくのをやめます。
カードは毎回1-10までセットされていて、同等の確率で出現するということです。
問題はアリスがnの数以下をもっている確率を答える、というもの。
いや、３つも数つかうなよ、って感じですね。w
一度よんだだけでは意味がわかりません。
スポンサーリンク
解法
maxPts=10, k=17, n =21の場合を考えます。
回答はずばりPをprobabilityとすると、、P(21) + P(20) + P(19) + P(18)+ P(17)ですね。
アリスが引くカードの合計がk=17になったら引くのをやめるので、P(17) ~ P(21)までの確率を足し合わせればOKです。
では、P(21)に焦点をあてて、この数はどうやって算出するのでしょうか。
P(21) = P(16) * P(5) +
P(15) * P(6) +
P(14) * P(7) +
…
P(21-maxPts) * P(maxPts)
と表現できます。なぜP(16)から始まるのかというと、kが17なのでkより小さい値（k-1)の値から始まります。
またP(5)の部分に関して、P(1)の確率も、P(maxPts)の確率も同等に1/maxPtsなので、計算式としては省略できます。
つまりP(i) = 1/maxPts * ( P(k-1) + P(k-2) + …. + P(i-maxPts))と表現できます。
さらに詳細を見ていくと、
P(18) = 1/maxPts *( P(16) + P(15) + .. P(8) ) // maxPtsが10なので、18-10 で8
P(17) = 1/maxPts *( P(16) + P(15) + .. P(8) + P(7))
P(16) = 1/maxPts * ( P(15) + P(14) + P(8) + P(7) + P(6) )
というふうに計算できるのですがP(18)とP(17)では計算が重複している箇所があります。p(7)以外
P(16)からP(17)を算出するにはSliding windowしており、P(16)が追加されP(6)が除外されています。
これをコードに落とすと以下の通りになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public double new21Game(int n, int k, int maxPts) { if(k ==0 || n >= k+maxPts ){ return 1; } double[] dp = new double[n+1]; dp[0] = 1; double curSum = dp[0]; for(int i = 1; i<= n;i++){ dp[i] = curSum / (double)maxPts; if( i < k){ curSum +=dp[i]; } if( i - maxPts >= 0 ){ curSum -= dp[i - maxPts]; } } double ans = 0; for(int i = k ; i<=n; i++){ ans += dp[i]; } return ans; } } |
