Good Bye 2015 : E. New Year and Three Musketeers

本番グダり過ぎて、最終的にACしたけど微妙な点数だった。
http://codeforces.com/contest/611/problem/E

問題

強さA,B,Cの3人の戦士でN匹の敵を倒す。
各敵の強さはT[i]である。

時間1あたり、各戦士は任意の敵1体をターゲットとできる。
ある敵と戦う戦士の強さの合計が敵の強さ以上であればその敵を撃破できる。
全敵を撃破するまでにかかる最短時間を求めよ。

解法

1≦A≦B≦Cとする。
3人の組み合わせ方により、強さの順番はA≦B≦(C,A+B)≦A+C≦B+C＜A+B+Cとなり、CとA+Bの関係以外は一意に順番が決まる。
よって、まず以下を求めよう。

• A+B+Cでなければ倒せない敵の数
• 残りのうち、B+Cでなければ倒せない敵の数。この際、同じ数だけAは単独行動出来る。
• 残りのうち、A+Cでなければ倒せない敵の数。この際、同じ数だけBは単独行動出来る。

ここまで来ると、残りの敵をA,B,C,A+Bの組み合わせで撃破する最短時間を求めたい。
二分探索でd日で残りを撃破できるか求めよう。

まず、Cは単独行動確定なので、Cが倒せる強さ上位d匹を倒す。
次に、B単独では倒せない敵は、最大d匹まで(A+B)で倒す。
残りをA,B単独で倒しきる。この際、上記(B+C)、(A+C)で敵を倒した際に余ったA,Bの単独行動回数も加味する。
これで全敵を倒しきれるか1回O(N)で判定可能。

int N;
int V[5];
int T[202020];
int did[202020];

int ok(int d,int n0,int n1) {
	int D[5]={d,d,d,0};
	int left=N,i;
	ZERO(did);
	for(i=N-1;i>=0;i--) if(did[i]==0 && D[2]&& T[i]<=V[2]) D[2]--, left--, did[i]=1;
	for(i=N-1;i>=0;i--) if(did[i]==0 && D[0]&&D[1]&& T[i]>V[1]&&T[i]<=V[0]+V[1]) D[0]--,D[1]--,left--, did[i]=1;
	D[1]+=n1;
	D[0]+=n0;
	for(i=N-1;i>=0;i--) if(did[i]==0 && D[1]&& T[i]<=V[1]) D[1]--, left--, did[i]=1;
	for(i=N-1;i>=0;i--) if(did[i]==0 && D[0]&& T[i]<=V[0]) D[0]--, left--, did[i]=1;
	
	return left==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,3) cin>>V[i];
	FOR(i,N) cin>>T[i];
	sort(V,V+3);
	sort(T,T+N);
	if(T[N-1]>V[0]+V[1]+V[2]) return _P("-1\n");
	
	int ret=0;
	x=0;
	while(N && T[N-1]>V[1]+V[2]) { // need ABC
		assert(T[N-1]<=V[0]+V[1]+V[2]);
		N--, ret++;
	}
	int n0=0,n1=0;
	while(N && T[N-1]>V[0]+V[2]) { // need BC
		assert(T[N-1]<=V[1]+V[2]);
		N--, ret++,n0++;
	}
	while(N && T[N-1]>max(V[2],V[0]+V[1])) { // need AC
		assert(T[N-1]<=V[0]+V[2]);
		N--, ret++,n1++;
	}
	
	int ret2=(1<<20)-1;
	for(i=19;i>=0;i--) if(ok(ret2-(1<<i),n0,n1)) ret2-=1<<i;
	
	cout<<ret+ret2<<endl;
}

まとめ

シンプルな問題設定だけど、意外に既出ではない…？