TopCoder SRM 818 : Div1 Medium PStepsGame

最近の500pt Mediumではトップクラスに簡単な問題じゃないか？
https://community.topcoder.com/stat?c=problem_statement&pm=17253&rd=18920

問題

N人の参加者がおり、以下の催しを行う。
P組の瓶がある。各組は、水の入った瓶と酢の入った瓶があり、初期状態ではどちらがどちらかわからない。
N人順次以下を繰り返す。

• 任意の組の任意の瓶を選び、中身を飲む。
  • 中身が水ならその人の番は終了。酢ならその人は敗退する。
  • 自分及び他人がどの瓶を選び、結果がどうなったかは皆が共有している。
• 全部の組で水を選んだ人は、クリア扱いとなり催しから抜ける。

皆が最適手を打つとき、クリア扱いとなる人数の期待値を求めよ。

解法

• 参加者の区別がないので、参加者の順番は無視してよく、人数だけ考慮すればよい。
• 1人が未知の組み合わせの瓶を1つ飲んだ時、水にせよ酢にせよその組の瓶のうち水のものが確定するので、未知の瓶の組は1つ減る。

上記考察より、
f(n,p) := 残りn人催しに残っており、水・酢の区別が未知の瓶の組がp個あるときの、クリア人数の期待値
とすると、f(N,P)が解となる。

• f(n,0) = n
• f(0,p) = 0
• f(n,p) = (f(n-1,p-1)+f(n,p-1))/2

となるのでO(NP)でf(N,P)を計算できる。

double dp[5050][5050];

class PStepsGame {
	public:
	double solve(int N, int P) {
		
		ZERO(dp);
		int i,x,y;
		FOR(x,5050) dp[x][0]=x;
		for(i=1;i<=N;i++) {
			for(x=1;x<=P;x++) {
				dp[i][x]=(dp[i][x-1]+dp[i-1][x-1])/2.0;
			}
		}
		return dp[N][P];
		
	}
}

まとめ

400ptでもいいぐらいの問題に思えた。