Zepto Code Rush 2014 : E. Cardboard Box

一見簡単そうで意外と難しい…と思ったら実は簡単。
http://codeforces.com/contest/436/problem/E

問題

N個のステージがあり、それぞれ時間A[i]をかけて星１つ、時間B[i]をかけると星２つが手に入る。
合計W個の星を得るのに必要な最短時間を答えよ。

解法

Editorialよりも、上位陣の回答の方がわかりやすい。

考えかたは単純で、1つのステージで2つ星を取る方が、2つのステージで1つずつ星を取るより短い時間で2つの星を取れる、と判断すると、前者でまず1つの星を取る。
そうでない限りは、短い時間で星を取れる順に1ステージずつ選んでいけばよい。

int N,W;
int A[400000],B[400000];
set<pair<int,int> > S1,S2;
pair<int,int> P[400000];
int ok[400000],ok2[400000];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>W;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		S1.insert(make_pair(A[i],i));
		S2.insert(make_pair(B[i],i));
	}
	
	ll ret=0;
	FOR(i,W) {
		if(i<W-1 && !S2.empty() && S1.size()>1) {
			pair<int,int> p1=*S1.begin();
			S1.erase(S1.begin());
			pair<int,int> p2=*S1.begin();
			S1.erase(S1.begin());
			if(S2.begin()->first < p1.first+p2.first) {
				pair<int,int> p=*S2.begin();
				S2.erase(S2.begin());
				ret+=A[p.second];
				ok[p.second]++;
				S1.insert(p1);
				S1.insert(p2);
				S1.erase(make_pair(A[p.second],p.second));
				S1.insert(make_pair(B[p.second]-A[p.second],p.second));
				continue;
			}
			S1.insert(p1);
			S1.insert(p2);
		}
		pair<int,int> p=*S1.begin();
		S1.erase(S1.begin());
		ret+=p.first;
		ok[p.second]++;
		if(ok[p.second]==1) {
			S2.erase(make_pair(B[p.second],p.second));
			S1.insert(make_pair(B[p.second]-A[p.second],p.second));
		}
	}
	
	_P("%lld\n",ret);
	FOR(i,N) _P("%d",ok[i]);
	_P("\n");
}

まとめ

本番、Google Code Jam 2012 Round1A B. Kingdom Rushが思いついた。
https://code.google.com/codejam/contest/1645485/dashboard#s=p1