TopCoder SRM 628 Div1 Hard DoraemonPuzzleGame

本番あと一歩で解けそうだったのに時間切れ。
http://community.topcoder.com/stat?c=problem_statement&pm=13283

問題

N個のステージがある。
各ステージに1回挑戦すると、確率X[i]で星1個、確率Y[i]で星2個取得できる。
各ステージは複数回挑戦しても良いが、得られる星の数は過去の複数回の挑戦の最大値である。

これらN個のステージでm個の星を集めたい。
ただし、各ステージ最低1個は星を取らなければならない。

最適な手順でステージを選択する場合、ステージ挑戦回数の期待値を答えよ。

解法

(m-N)個のステージは星2個を取らなければならない。
星2個を狙うのは当然Y[i]が高いステージがお得なので、ステージはY[i]でソートして挑戦する。

各ステージ、星2個を取ったステージ数を状態としてDPし、その状態の到達確率と挑戦回数の期待値を数えていく。
各ステージでは、そのステージで星2個取らないとm個に到達しない場合は2個とるまで挑戦し、そうでないなら1個取れたら次のステージに移動する。

本番は下記挑戦回数の正規化(dp[i][x]/=prob[i][x];)をやり忘れて通らなかった…。

double prob[2001][2001];
double dp[2001][2001];

class DoraemonPuzzleGame {
	public:
	pair<int,int> P[2001];
	double solve(vector <int> X, vector <int> Y, int m) {
		int N=X.size(),i,x;
		
		FOR(i,N) P[i]=make_pair(Y[i],i);
		m-=N;
		sort(P,P+N);
		
		ZERO(prob);
		ZERO(dp);
		
		prob[0][0]=1;
		FOR(i,N) {
			int t=P[i].second;
			
			FOR(x,m+1) if(prob[i][x]>0) {
				double mul=1000.0/(X[t]+Y[t]);
				
				dp[i][x]/=prob[i][x];
				if(x>=m) {
					prob[i+1][x]+=prob[i][x];
					dp[i+1][x]+=prob[i][x]*(dp[i][x]+mul);
				}
				else if(x+(N-i)==m) {
					prob[i+1][x+1]+=prob[i][x];
					dp[i+1][x+1]+=prob[i][x]*(dp[i][x]+1000.0/Y[t]);
				}
				else {
					prob[i+1][x+1]+=prob[i][x]*Y[t]/(double)(X[t]+Y[t]);
					prob[i+1][x]+=prob[i][x]*X[t]/(double)(X[t]+Y[t]);
					dp[i+1][x+1]+=prob[i][x]*Y[t]/(double)(X[t]+Y[t])*(dp[i][x]+mul);
					dp[i+1][x]+=prob[i][x]*X[t]/(double)(X[t]+Y[t])*(dp[i][x]+mul);
				}
			}
		}
		
		return dp[N][m];
	}
}

まとめ

1000ptのHard解けるチャンスだったのにもったいない。