Codeforces Round #146 Let's Play Osu!

問題概要

Osuと呼ばれるゲームをする。連続するx個の○についてx²の得点が与えられる。 n文字の文字列が与えられるので、得点の期待値を求める。ただし、i番目の文字が○である確率はp_iである。

方針

n² = 2 * _nC₂ + n

という関係から以下のような問題の読み替えができる。
「連続する○について○の長さの2乗が加点される。」→ 「一つの○につき1点加点し、○のペアについて間に×が一つもなければ2点加点する。」
これを利用して期待値を計算する。後半のペアうんぬんのところは動的計画を使って計算する。

ソースコード

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

int main() {
    int n;
    static double p[100000];
    cin >> n;

    REP(i, n) scanf("%lf", p+i);

    double ret = 0;
    double q = 0;
    REP (i, n) {
        ret += p[i];
        if (i > 0)
            q = (q + p[i-1]) * p[i];
        ret += 2*q;
    }

    printf("%.8lf\n", ret);
    return 0;
}