yukicoder No.65 回数の期待値の練習

問題

問題概要

サイコロを降って、目の合計がK以上になるサイコロを振る回数の期待値を求める問題。

解法

漸化式を用いて動的計画法で解く。

ミス

漸化式をすこし間違えた。dp[i] := (これまでの目の合計が i のとき、合計が k になるまでに降ることになる回数の期待値)とおく。初期値が重要。目の合計がk以上なら、それ以上サイコロを振らなくていいので、dp[k]=0となる。k < iも同様である。
漸化式は目の合計はiのときは目の合計がi + 1, i + 2, ..., i + 6を利用して求めることができる。たとえば、これまでの合計がiと合計i + 1のときを例として考える。iからi + 1へ合計が1増加しているのはサイコロの目が1出たということである。合計iのときの期待値は、(1 + (合計i + 1の時の期待値)) * 1/6となる。1はサイコロを１回振ったことから足している。1/6はサイコロの１の目が1/6で出るからである。ほかの場合も同様に考えるだけ。

コード

#include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

const int max_k = 30;
double dp[max_k];
//dp[i] := これまでの目の合計が i のとき、合計が k になるまでに降ることになる回数の期待値
//dp[k] = 0; 求める解dp[0]

int main(void){
    int k; cin >> k;
    dp[k] = dp[k + 1] = dp[k + 2] = dp[k + 3] 
    = dp[k + 4] = dp[k + 5] = dp[k + 6] = 0;
    for (int i = k - 1; i >= 0 ; --i){
        dp[i] = (1.0 + dp[i + 1]) * (1.0 / 6.0) +
                (1.0 + dp[i + 2]) * (1.0 / 6.0) +
                (1.0 + dp[i + 3]) * (1.0 / 6.0) +   
                (1.0 + dp[i + 4]) * (1.0 / 6.0) +   
                (1.0 + dp[i + 5]) * (1.0 / 6.0) +
                (1.0 + dp[i + 6]) * (1.0 / 6.0);
    }
    printf("%f\n", dp[0]);

    return 0;
}