Codeforces 277D (170D) Google Code Jam

問題

t分間にわたってgoogle code jam形式のコンテストを行う。

n問の問題があり、それぞれsmall largeにわかれている。
smallを解くのにかかる時間、largeを解くのにかかる時間が問題ごとに与えられる。
smallを解くと得られる得点、largeを解くと得られる得点も問題ごとに与えられる。

smallは100%の確率で通すことができ、largeは、問題ごとに異なる失敗する確率がある。
失敗はコンテスト終了後に判明する。

得られる得点の期待値を最大にしたい。
得点の期待値が同じ中でも、ペナルティの期待値を最小にしたい。
ペナルティは、最後に正解した問題の時間である。

得点の期待値とペナルティの期待値を求めよ。

制約条件

n≦1000
t≦1600

方針

得点の期待値を最大にするには、
dp[時間]のテーブルを更新するDPをすればよい。

その中で、ペナルティの期待値を最小にすることを考える。
SとLのうち、解くものを決めた時、どういう順序で解くのが最適か。
まず、SSSSSLLLLLのように、Lが最後に並ぶのが明らかに最適であることはわかる。
その中で、Lの順序を決めたい。

二つのL、L1, L2があって、それぞれ解く時間をt1, t2、正解率をp1, p2とすると、
入れ替えた場合に損するのは、
(t1 + t2) * p2 + (1 - p2) * p1 * t1 <
(t1 + t2) * p1 + (1 - p1) * p2 * t2
のとき。
なぜなら、L1, L2と並んでいるときこの二つ以外のLの順序は同一なので無視してよくて、
t1 + t2のペナルティが入るのがp2を正解したとき
t1のペナルティが入るのがp2を不正解でp1を正解したときだから。

したがってこれが成り立つようにソートしてやればよいことがわかる。
使う順序がわかったら、この順序でDPするだけになる。

本番は誤差で落ちた。long doubleにしたら通った。

ソースコード

typdef long double ld;
const ld EPS=1e-12, INF=1e12;

struct P{
	int ss, sl, ts, tl;
	ld p;
	P(int a, int b, int c, int d, ld e):ss(a), sl(b), ts(c), tl(d), p(e){}
	bool operator<(const P &o)const{
		return (tl + o.tl) * o.p + tl * (1 - o.p) * p
		< (tl + o.tl) * p + o.tl * (1 - p) * o.p;
	}
};
int n, t;
pair<ld, ld> dp[1600];

void update(pair<ld, ld> &a, ld x, ld y){
	if(a.first + EPS < x) a = mp(x, y);
	if(abs(a.first - x) < EPS && y + EPS < a.second) a = mp(x, y);
}

int main(){
	cin >> n >> t;
	vector<P> prob;
	rep(i, n){
		int ss, sl, ts, tl;
		ld p;
		cin >> ss >> sl >> ts >> tl >> p;
		prob.pb(P(ss, sl, ts, tl, 1 - p));
	}
	sort(all(prob));
	
	rep(i, n) for(int j = t; j >= 0; j--){
		int ss = prob[i].ss, sl = prob[i].sl;
		int ts = prob[i].ts, tl = prob[i].tl;
		ld p = prob[i].p;
		
		int nj = j + ts;
		if(nj <= t) update(dp[nj], dp[j].first + ss, dp[j].second + ts);
		
		nj = j + ts + tl;
		ld na = dp[j].first, nb = dp[j].second;
		na += ss + p * sl;
		nb = (ts + nb) * (1 - p) + nj * p;
		
		if(nj <= t) update(dp[nj], na, nb);
	}
	pair<ld, ld> ans = mp(0, 0);
	rep(i, t + 1) update(ans, dp[i].first, dp[i].second);
	cout << fixed << setprecision(20) << ans.first << " " << ans.second << endl;
	
	return 0;
}