CS Academy Expected Merge

リンク : https://csacademy.com/contest/archive/task/expected-merge/statement/

問題概要

マージソートのアルゴリズムと同様の関数を考えた時に、数列を半分にすることを繰り返す。奇数長の場合、区切られる場所は一意に定まらない。そこで、一様にランダムで分割する場合、各indexのiに関して、関数でiを含む数列の区間の長さの合計の期待値を求めよ。

解説

下の図は、入力が5の場合を考えている。4が含む数列の長さの合計の期待値を求めるときに(3,4,5)と(4,5)を見ることは、(1,2,3)と(1,2)を見ることが同じであることがわかる。
そこでdp[i][j]を長さiの数列のj番目を含む数列の区間の長さの期待値とすると、次の関数に行くときのindexの変化のみ計算すればよい。しかし、これでは空間時間ともにO(n²)になると思うかもしれないが、n→n/2→n/4と変化するため間に存在する多くは巡らない。よってO(n logn)となる。配列も前もって静的に用意してしまうとMLEになってしまう。

LL n;
vector<double>dp[110000];
double func(int i, int j) {
    if (i == 1)return 1;
    if (dp[i].size() == 0)dp[i].resize(i+1);
    if (dp[i][j] != 0)return dp[i][j];
    double ret = 0;
    if (i % 2 == 0) {
        ret += func(i / 2, j % (i / 2));
    }
    else {
        if (j == (i + 1) / 2) {
            ret += func((i + 1) / 2, j);
            ret += func((i + 1) / 2, 1);
        }
        else {
            if (j > (i + 1) / 2) {
                ret += func(i / 2, j - (i+1) / 2);
                ret += func((i + 1) / 2, j - (i) / 2);
            }
            else {
                ret += func(i / 2, j);
                ret += func((i + 1) / 2, j);
            }
        }
        ret /= 2.0;
    }
    ret += i;
    return dp[i][j] = ret;
}
int main() {
    cin >> n;
    rep(i, n) {
        if (i)cout << " ";
        printf("%.15f", func(n, i+1));
    }
    cout << endl;
    return 0;
}