- パンケーキが N 個あり、パンケーキ i の直径は i+1 でおいしさは d[i] である。残ってるパンケーキから等確率で 1 個選びある皿に乗せていく。
- 皿に乗ってる一番上のパンケーキの直径より大きなのが選ばれた時点で終了。取るやつがなくなっても終了。おいしさの期待値を求めよ。
- 1≦N≦250, 1≦d[i]≦1000
- DPが思いつかないので...
- 1/N! の確率で [1, N] の permutation p が選ばれることになる。これを p[i-1]＞p[i] である最大の i までについて Σd をとったものがその場合のおいしさ。
- 縦に N! 通り、横に permutation を書いていってどうにか規則的に足せないか考えていると...
- m+1 番目が X でありそれがおいしさにカウントされるような permutation の数は O(1) で求められることに気づく。
- ? ? ? X ? ?
- 前半は X より大きな N-x 個の数から m 個選び、後半は残りの N-m-1 個の順列なので Combination(N-x, m) * (N-m-1)!
- というわけで、全 m, X についてその場合の数 * d[X] を足して最後に N! で割ったものが答え。
- dp でやる場合は dp[Topの直径][今まで何個使ったか], dp[N][0]=1, 配った時パンケーキごとに使った数を覚えていくとよい模様。
#define D long double
class RandomPancakeStack {
public:
D fac(int x) {
D v = 1;
REP(i, x) v*=i+1;
return v;
}
D f(int x, int m, int N) {
int k = N-m-1;
if(N-x<m) return 0;
return fac(N-x)*fac(k)/(fac(m)*fac(N-x-m));
}
double expectedDeliciousness(vector <int> d) {
int N = d.size();
D ans = 0;
REP(v, N) {
D lans = 0;
REP(di, N) {
D z = f(v+1, di, N);
lans += z;
}
lans *= d[v];
ans += lans;
}
D div = fac(N);
return ans / div;
}
};
