Expected Merge [CSAcademy #47 D]

https://csacademy.com/contest/round-47/task/expected-merge/

解法

今回は実は[L,R]の分割法として取りうる範囲を全て試しても間に合う。
正直なんとなくで通した感があるのだが、アルゴリズムでやってることは以下の通り。

• [L,R)の範囲に(R-L)*pを足す
• (R-L)が偶数のとき（=割り方が一意に定まる場合）は確率pは変わらないのでそのままで2つに割る。
• (R-L)が奇数のとき（=割り方が一意でない場合）は確率pは、どちらかになるかの半分半分になるので、p=p/2として、2つに割る。
• [L,R)が1つの要素になったら、割らずに戻る

　
恐らく、期待値の線形性を使った問題かと思われる。

int N;
double ans[101010];
//---------------------------------------------------------------------------------------------------
void f(int L, int R, double p) {
    ans[L] += 1.0 * (R - L) * p;
    ans[R] -= 1.0 * (R - L) * p;
    if (L + 1 == R) return;
    int md = (R + L) / 2;
    if ((R - L) % 2 == 0) {
        f(L, md, p);
        f(md, R, p);
    } else {
        f(L, md, p / 2);
        f(md, R, p / 2);
        f(L, md + 1, p / 2);
        f(md + 1, R, p / 2);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    f(0, N, 1);

    rep(i, 1, N) ans[i] += ans[i - 1];

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%.10f", ans[i]);
    } printf("\n");