https://atcoder.jp/contests/dp/tasks/dp_i
前提知識
解説
https://atcoder.jp/contests/dp/submissions/3947967
確率DPをする。
dp[i][omote] := i枚のコインを投げて表の枚数がomoteとなる確率
uraを保持しなくてもいいのか?という問題があるが、ura=i-omoteなので保持しなくてもいい。
遷移は表が出る、裏が出るの二択。
あとは、ura<omoteとなる確率をすべて足せば答え。
数学の「積の法則」「和の法則」がしっかりわかってないと厳しい。
int N; double P[3010]; double dp[3030][3030]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> P[i]; dp[0][0] = 1; rep(i, 0, N) rep(omote, 0, N + 1) { dp[i + 1][omote] += dp[i][omote] * (1 - P[i]); dp[i + 1][omote + 1] += dp[i][omote] * P[i]; } double ans = 0; rep(omote, 0, N + 1) if (N - omote < omote) ans += dp[N][omote]; printf("%.10f\n", ans); }