Codeforces #170 Div1 D. Google Code Jam

問題文とEditorialは長いけど、難易度自体はそこまで高くない。
http://codeforces.com/contest/277/problem/D

問題

コンテストにN種類の問題がある。
各問題はsmallとlargeの2段階の回答があり、それぞれ回答するのにかかる時間TS[i]・TL[i]及びそれぞれのポイントSS[i]・SL[i]が与えられる。

参加者は問題を1問ずつ解いていく。各問題のsmall/largeの回答順は任意であるが、largeはsmallを正答した後でないと取り組めない。
また、largeの時間TL[i]・ポイントSL[i]はsmallとは別にそれぞれ加算される。

ここで、smallはTS[i]時間かければ正解となりSS[i]ポイントが得られることが確定している。
一方largeはTL[i]時間かけて解いたところで、正解かどうかは最後までわからない。
正解しない確率PF[i]は別途与えられる。

このコンテストの順位は、ポイントが大きいほどよく、ポイントが同点なら最後に解けた問題の時刻が早い方が優位である。
コンテストの時間がTあるときに、良い順位になるよう最適な問題取組順を取った場合、ポイントおよび最後に正答した時刻の期待値を答えよ。

解法

ポイントの最大化だけなら、正答時の各問題の期待値でDPするだけで良い。
O(NT)かかるがN,Tはさほど大きくないので問題ない。

問題は最終正答時刻の最小化である。
当然時間のかかりそうな問題を後回しにしておくと、正答しない場合により時刻を小さくすることができる。
具体的な計算はEditorialを参照してもらうとして、問題iとjはTL[i]*PF[i]/(1-PF[i]) ＜ TL[j]*PF[j]/(1-PF[j]) ならiのlargeを先解いた方が良い。

この順で問題をソートし、ポイントを最大化しつつ時刻を最小化するDPを行えばよい。
時刻の期待値の計算式が若干ややこしいので注意。

int N,T;
ll SS[1001],SL[1001],O[1001],TS[1001],TL[1001];
double PF[1001];

pair<ll,double> dp[2001];

bool cmp(int i,int j) {
	return TL[i]*PF[i]*(1-PF[j])<TL[j]*PF[j]*(1-PF[i]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>SS[i]>>SL[i]>>TS[i]>>TL[i]>>PF[i];
		SS[i]*=1000000;
		SL[i]*=1000000-(int)(PF[i]*1000000+0.1);
		O[i]=i;
	}
	sort(O,O+N,cmp);
	
	FOR(i,N) {
		int tar=O[i];
		for(x=T-1;x>=0;x--) {
			if(x+TS[tar]<=T) {
				double dd=dp[x].second+TS[tar];
				if(dp[x+TS[tar]].first<dp[x].first+SS[tar] ||
				  (dp[x+TS[tar]].first==dp[x].first+SS[tar] && dp[x+TS[tar]].second>dd)) 
					dp[x+TS[tar]]=make_pair(dp[x].first+SS[tar], dd);
			}
			if(x+TS[tar]+TL[tar]<=T) {
				double dd=TS[tar]+PF[tar]*dp[x].second+(1-PF[tar])*(x+TL[tar]);
				if(dp[x+TS[tar]+TL[tar]].first<dp[x].first+SS[tar]+SL[tar] ||
				  (dp[x+TS[tar]+TL[tar]].first==dp[x].first+SS[tar]+SL[tar] &&
				   dp[x+TS[tar]+TL[tar]].second>dd)) 
				dp[x+TS[tar]+TL[tar]]=make_pair(dp[x].first+SS[tar]+SL[tar], dd);
			}
		}
	}
	
	ll ma=0;
	double mi=1e15;
	FOR(i,T+1) if(dp[i].first>ma || (dp[i].first==ma && dp[i].second<mi)) ma=dp[i].first, mi=dp[i].second;
	_P("%.9lf %.9lf\n",ma/1000000.0,mi);
	
}

まとめ

問題文とEditorialのややこしさで損してるな。