POJ 3941 - Expected Allowance

http://poj.org/problem?id=3941

概要

\(n\) 個の \(m\) 面ダイスがある。 各ダイスには \(1, \cdots, m\) の数字が書かれている。 これらの \(n\) 個のダイスを振って出た数字の合計から \(k\) を引いた値の期待値を答える。 ただし、\(k\) を引いた結果が0以下になった場合の値は \(1\) とする。

制約

• \(1 \le n\)
• \(2 \le m\)
• \(0 \le k < nm\)
• \((nm) ^ 2 < 10 ^ 8\)

解法

dp[i][j] := i 個目のダイスまで考えたときに、合計値が j である確率

として、

dp[i+1][j+k] += dp[i][j] * 1.0/m   for k = 1 .. m

と更新していく。 DP 表のサイズが \(\mathrm{O}(n ^ 2 m)\)、更新コストが \(\mathrm{O}(m)\) なので、 全体の計算量は \(\mathrm{O}(n ^ 2 m ^ 2)\) になる。 ただし、DP 表を更新するときは直前の表しか参照しないので、2つを使い回すことでメモリを節約できる。

これで各値をとりうる確率が計算できるので、あとは普通に期待値を計算すればいい。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, M, K;
 8   while (scanf("%d %d %d", &N, &M, &K) != EOF && N != 0) {
 9     static double dp[10001], dp_next[10001];
10     fill_n(dp, N*M+1, 0.0);
11     dp[0] = 1.0;
12     for (int i = 0; i < N; i++) {
13       fill_n(dp_next, N*M+1, 0.0);
14       for (int j = 0; j < N*M; j++) {
15         for (int k = 1; k <= M; k++) {
16           dp_next[j+k] += dp[j] * 1.0/M;
17         }
18       }
19       swap(dp, dp_next);
20     }
21     double ans = 0;
22     for (int i = 0; i <= N*M; i++) {
23       if (i <= K) {
24         ans += dp[i];
25       } else {
26         ans += dp[i] * (i-K);
27       }
28     }
29     printf("%.8f\n", ans);
30   }
31   return 0;
32 }