SRM 656 Div1 Easy - RandomPancakeStack

問題

TopCoder Statistics - Problem Statement

問題概要

枚のパンケーキがある。それらのパンケーキは~までの番号が振られており、番目のパンケーキは大きさがでおいしさがである。パンケーキをいくつか選んでプレートにのせてタワー状のパンケーキを作ろうと思う。そのとき、以下の様な手順でプレートをつくる：

1. まず、枚の中からランダムに1枚パンケーキを選んでのせる。
2. もう残っているパンケーキがなければ終了する。
3. 残っているパンケーキの中からランダムに1枚のパンケーキを選ぶ。そして、選ばれたパンケーキの大きさが現在プレートにのっている一番上のパンケーキよりも大きいなら、そのパンケーキをのせずに操作を終了する。
4. 選ばれたパンケーキをプレートの一番上にのせ、2.に戻る。

この操作を終了した時にプレートに乗っているパンケーキ全てのおいしさの合計をそのプレートのおいしさとする。今、が与えられるのでプレートのおいしさの期待値を求めよ。

• 
• 

アイデア

大きさが0のパンケーキが直感的にわかりにくいので問題では番目のパンケーキの大きさがとなっているが、別にとして考えても特に差し支えは無いので、以下では大きさをそのように扱う。

番目のパンケーキがプレートの一番上にある時に、それ以降の操作で得られるおいしさの合計の期待値をとすると、はじめの1枚がランダムに選ばれることを考えれば求める答えは期待値の線形性よりとなる。以下では、を求めることについて考えよう。

プレートに今枚のパンケーキがのっている時、残っているパンケーキは枚である。次のパンケーキはこの枚のうちのどれか1つから選ばれるわけであるが、ここで選ばれたパンケーキがプレートの一番上のパンケーキよりも大きいなら操作が終了する。ということは、この時はこれ以降の期待値は0になる。逆に、小さければパンケーキをプレートの一番上にのせて、その後も操作が続行していくことになる。つまりこの状態での期待値は、全ての正しい遷移に対して番目のパンケーキが一番上でプレート上に枚あるものの合計をで割ったものということになる。

つまり、ここまでのことをまとめるとの情報として「今プレートの一番上にあるパンケーキの大きさ」と「プレート上にあるパンケーキの数」が必要になるわけである。ここで、プレート上の状態全てを知る必要はない。なぜなら、この2つがわかっていればまずプレート上により小さいパンケーキがのっていることはあり得ないので~までのパンケーキはまだ残っていることがわかるからである。そしてその正しい遷移の期待値を足して割るためにがあればよいということになる。

この期待値をと表すことにすれば、ということになる。よって、このを全て計算するためにはかかるが、であることを考えれば十分である。

そして、この期待値の設定から、最終的に答えるべきものはということになる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

class RandomPancakeStack {
    public:
    double expectedDeliciousness(vector<int> d) {
        int n=d.size();
        double E[251][251]={0};

        for(int w=1; w<=n; ++w)rep(s,n)
        {
            rep(i,w) E[w][s] += d[i]+E[i][s+1];
            E[w][s]/=n-s;
        }

        return E[n][0];
    }
};