kmjp's blog

競技プログラミング参加記です

TopCoder SRM 656 Div1 Easy RandomPancakeStack、Div2 Medium RandomPancakeStackDiv2

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;
	}
}

まとめ

これは割とすんなり解けて良かった。