mayoko’s diary

プロコンとかいろいろ。

SRM 656 div1 easy:RandomPancakeStack

SRM 656に参加。結果は190ptくらいでeasyを提出できて自分にしては良い感じのスコアで終了。レーティングも1524と黄色に上がれて個人的な最低限の目標も達成できて結構嬉しいです。

問題:後で貼ります

解法:まず「i番目のケーキを選んだらもうi+1番目以降のケーキは取れない」ということに注目する。これにより,状態として「今一番上にあるケーキはなにか」と「今までに何個のケーキを載せたか」という情報があれば,dpに持ち込めそうな気がしてくる。
具体的には,以下のようにやる。
dp[cur][used]=(今載せようとしているケーキがcurで,今までにケーキをused個載せた時の美味しさの期待値)とする。すると,curのケーキの分の美味しさは期待値の中に入ってきて,さらにcur未満のケーキを載せることのできる可能性がある。載せられるケーキは0〜cur-1のいずれかで,それぞれを選ぶ確率は1/(n-used)である(もしかしたらcurよりでかいケーキを選んで試合終了してしまう可能性があることに注意。そのためにusedという変数が必要になっている)。それについても再帰で期待値を計算していけばdp[cur][used]の値を決定できる。
答えを求めるときは,i=0〜n-1について「iを選んで今までに1個選んだ」という状態になるのでそれぞれについて和を求めれば良い。
以下ソースコード

vector<int> d;
double dp[300][300];

double dfs(int cur, int used) {
    if (cur == 0) return d[0];
    double & ret = dp[cur][used];
    if (ret >= 0) return ret;
    int n = d.size();
    int rest = n-used;
    ret = d[cur];
    for (int i = 0; i < cur; i++) {
        ret += dfs(i, used+1) / rest;
    }
    return ret;
}

class RandomPancakeStack {
public:
    double expectedDeliciousness(vector <int> D) {
        d = D;
        for (int i = 0; i < 300; i++) {
            for (int j = 0; j < 300; j++) {
                dp[i][j] = -1;
            }
        }
        int n = d.size();
        double ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dfs(i, 1) / n;
        }
        return ans;
    }
};