Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}