AOJ1286 Expected Allowance

Expected Allowance | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

として，シュミレーション．サイコロを振るのは と書ける．配列を再利用するために，の偶奇を見て遷移する．次に遷移する場所に値が残っているとおかしいことになるので，からサイコロを振ったらそこは初期化する．分母は全て で， 引いた時に最低でも になるようにして期待値を求める．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int dp[2][100005];

int main() {
  int n, m, k;
  while(cin >> n >> m >> k) {
      if(n == 0 && m == 0 && k == 0) break;

      memset(dp, 0, sizeof(dp));
      REP(j, 1, m + 1) {
          dp[1][j] = 1;
      }

      rep(i, n) {
          rep(j, 100005) {
              if(dp[i & 1][j] == 0) continue;
              REP(k, 1, m+1) {
                  dp[(i+1)&1][j+k] += dp[i&1][j];
              }
              dp[i&1][j] = 0;
          }
      }

      double ans = 0, t = 1;
      rep(i, n) {
          t *= m;
      }

      rep(j, 100005) {
          if(dp[n&1][j] == 0) continue;

          double l = j - k;
          if(l <= 0) l = 1;
          ans += (dp[n & 1][j] / t) * l;
      }

      cout << fixed;
      cout.precision(20);
      cout << ans << endl;
  }

  return 0;
}
Mar 18th, 2016
250, aoj-icpc, 動的計画法, 期待値