【SRM656Div1】RandomPancakeStack【250point】

問題概要

$N$個のパンケーキがある. それぞれパンケーキには大きさとおいしさというパラメータが定められており, 大きさ$i$のパンケーキの美味しさは$d[i]$である.

今, 以下の手順にしたがってパンケーキを重ねていく.

1. もう取れるパンケーキがないなら終了.
2. まだ取っていないパンケーキを, どれか無作為に取る.
3. それが最後に取ったパンケーキよりも大きければ終了する.
4. 1に戻る.

こうしてできたパンケーキタワーの美味しさを, 各パンケーキの美味しさの総和として定義するとき, パンケーキタワーの美味しさの期待値を求めなさい.

制約

• $1 \leq N \leq 250$
• $1 \leq d_i \leq 1000$

考察

DPなことはわかったけどどうやって定義すれば良いのか分からず.

有識者によると, 「$dp[i][j] := $既に$j$個食べていて, $i$以降食べれるときの期待値」と定義すればいいらしい.

遷移

1個目以降に食べたやつは$\displaystyle\frac{1}{N}倍$, 2個目以降に食べたやつは$\displaystyle\frac{1}{N - 1}$倍みたいな感じになってるので,

2個目を食べるとき, (今食べたもののおいしさ) + (3個目以降の期待値)を$\displaystyle\frac{1}{N - 1}$倍したものを返せば良い感じになる.

これを式にすると以下のようになる.

$$ dp[i][j] = \frac{\sum^N_{k=i}{d[k] + dp[k + 1][j + 1]}}{N - j} $$

反省

こういう期待値DP苦手. どのタイミングで割れば良いのかがわかんなくなりがち.

提出コード(C++🔆)

struct RandomPancakeStack {
    int N;
    vector<int> d;
    double dp[255][255];
    // すでにate個食べていて, cur以降食べれるときの残りの期待値
    double rec(int cur, int ate) {
        if (dp[cur][ate] != -1) return dp[cur][ate];
        double ret = 0.0;
        for (int nxt = cur; nxt < N; ++nxt) {
            ret += double(d[N - 1 - nxt] + rec(nxt + 1, ate + 1)) / (N - ate);
        }
        return dp[cur][ate] = ret;
    }
    double expectedDeliciousness(vector<int> _d) {
        d = _d, N = (int)_d.size();
        REP(i, 255) REP(j, 255) dp[i][j] = -1;
        return rec(0, 0);
    }
};