Codeforces 235B - Let's Play Osu!
問題文 : Let's Play Osu!
概要
$n$ 個のマスがある. マス $i$ は確率 $p_i$ で "○" になり, 確率 $1 - p_i$ で"×"になる.$n$ 個のマスのうち, "○"で繋がったそれぞれの連結成分の大きさを$S_i$ とすると, スコア $\displaystyle\sum_{i = 1}^{連結成分数}S_i^2$ を得る. スコアの期待値を求めよ.
制約
- $1 \leqq n \leqq 10^5$
- $0 \leqq p_i \leqq 1$
解法
$i$ 番目のマスを最後とした連結成分の大きさの期待値を $E[\text{len}[i]]$ とすると,$E[\text{len}[i]] = p_i \times (1 + E[\text{len}[i - 1]])$ という漸化式が成り立つ.
スコアの増分は, $E[(\text{len}[i] + 1) ^2] - E[\text{len}[i]^2] = 2 \times E[\text{len}[i]] + 1$ となる. これを前回までのスコアの期待値に足していけばOK.
コード
#include <bits/stdc++.h> using namespace std; int main() { int n; double p, cur, ans; scanf("%d", &n); cur = ans = 0; for (int i = 1; i <= n; i++){ scanf("%lf", &p); ans = p * (1 + 2 * cur) + ans; cur = p * (1 + cur); } printf("%.10lf\n", ans); return (0); }