yukicoder No.301 サイコロで確率問題 (1)
解法
N が十分大きい時は N+(5/3) に収束します。
他の場合は No.75 と同じです。mayokoex.hatenablog.com
が, 別の方法で解きました。
各 dp[i] は dp[0] の線形で書けるので, dp[0] = a0 * dp[0] + b0
という形になります。この a0 と b0 を漸化式から求めて dp[0] を計算します。
なんかよくわからないんですが
cin.tie(0);
ios::sync_with_stdio(false);
って書くと printf で double を書こうとすると死ぬっぽいです。
void solve(int K) { vector<double> a(K+6), b(K+6); for (int i = K+1; i < K+6; i++) a[i] = 1; for (int i = K-1; i >= 0; i--) { b[i] = 1; for (int j = 1; j <= 6; j++) { a[i] += a[i+j]/6; b[i] += b[i+j]/6; } } printf("%.15lf\n", b[0]/(1-a[0])); } int main() { int T; cin >> T; while (T--) { ll N; cin >> N; if (N <= 1000) { solve((int)N); } else { cout << N+1 << ".666666666666667" << endl; } } return 0; }