yukicoder No.75 回数の期待値の問題

問題

No.75 回数の期待値の問題 - yukicoder

解法

冷静に漸化式を立てます。

dp[i] = (今のマスが i の時にゴールするために必要なサイコロをふる回数の期待値)とすると,

dp[i] = 1/6 * dp[i+1] + ... + 1/6 * dp[i+6]

とします。求めたいのは dp[0] ですね。この漸化式は連立方程式を立てることで求められますが, ガウス・ザイデル法というのを用いると何回も上記の漸化式を繰り返すことで目的の値を求めることが出来ます。はい。

double solve(int K) {
    vector<double> dp(K+6);
    for (int t = 0; t < 10000; t++) {
        for (int i = 0; i < K; i++) {
            double tmp = 6;
            for (int j = 1; j <= 6; j++) {
                if (i+j > K) tmp += dp[0];
                else tmp += dp[i+j];
            }
            dp[i] = tmp/6;
        }
    }
    return dp[0];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    printf("%.14lf\n", solve(K));
    return 0;
}