SRM656に参加。
Easy早解きだけだったけど、Mediumの正答率が低かったのでレートが上昇した。
http://community.topcoder.com/stat?c=problem_statement&pm=13747
http://community.topcoder.com/stat?c=problem_statement&pm=13749
問題
N個のパンケーキがある。
i番目のパンケーキの幅はiでおいしさはD[i]である。
以下の処理を行ったとき、お皿に乗ったパンケーキのおいしさの総和の期待値を求めよ。
- 残りのパンケーキが1個もなければ終了。
- 残ったパンケーキのうち、等確率で1個選び、お皿の上に積み重ねていく。
- ただし、下に既にパンケーキがあり、かつ上に乗せるパンケーキの方が幅が大きい場合、上に乗せずに終了。
- パンケーキを上に乗せられた場合、上記処理を繰り返す。
Div2 MediumはDiv1 Easyより数の上限が小さいだけで中身は同じ。
解法
DP[最上位の幅][皿の上のパンケーキの数]=その状態に至る確率 として幅の大きい順にこの値を更新していく。
DP[w][i]からは、より小さいパンケーキj番がそれぞれ1/(N-i)の確率で選択される。
その際、DP[j][i+1] += DP[w][i]/(N-i)で確率を更新しつつ、おいしさの総和の期待値に適宜D[j]*DP[w][i]/(N-i)を加算していく。
class RandomPancakeStack { public: double D[300][300]; double expectedDeliciousness(vector <int> d) { int i,x,y,w; int N=d.size(); double ret=0; ZERO(D); D[N][0]=1; for(w=N;w>=0;w--) { FOR(i,N-w+1) if(D[w][i]) { FOR(x,w) { double prob=1.0/(N-i); D[x][i+1]+=D[w][i]*prob; ret += D[w][i]*prob*d[x]; } } } return ret; } }
まとめ
これは割とすんなり解けて良かった。