yukicoder : No.507 ゲーム大会(チーム決め)

2問目で手間取りました。
http://yukicoder.me/problems/no/507

問題

N人で2名ずつチームを組み参加するゲーム大会がある。
2人の参加者の獲得スコアの合計がチームのスコアとなる。

全員のスコアがわかっているとき、1番目の参加者がチームスコアで確実に上位M位に入るためには、何点以上の人と組むのが良いか。

解法

二分探索で解く。
1番目の人が組む人のスコアを決めたとき、M位以内に入るかどうかを判定しよう。
M位以内に入るということは、自分よりスコアの高いチームがM個以上構成できないことと同じである。

よって、1番目の人およびそのチームメイトを除いた(N-2)名で、1番目の人のチームスコアを最大何個作れるかを求めてみよう。
チームを組んでいない人のうち最大スコアの人に対し、合計スコアが1番目の人のチームを超える最小スコアの人をペアにする、ということを繰り返そう。
尺取り法の要領でペアの人を決めていけば、O(N)でそのようなチームの数を求めることができる。

int N,M,K;
int A[101010];

int ok(int ID) {
	if(ID<0) return 0;
	int T=K+A[ID];
	vector<int> V;
	int i;
	FOR(i,N) if(i!=ID) V.push_back(A[i]);
	
	int ret=0;
	int L=0,R=V.size()-1;
	while(L<R) {
		while(L<R && V[R]+V[L]<=T) L++;
		if(L>=R) break;
		ret++;
		L++,R--;
	}
	return ret<M;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	cin>>K;
	FOR(i,N-1) cin>>A[i];
	N--;
	sort(A,A+N);
	int R=N-1;
	if(ok(R)==0) return _P("-1\n");
	
	for(i=20;i>=0;i--) if(ok(R-(1<<i))) R-=1<<i;
	cout<<A[R]<<endl;
	
}

まとめ

実装はともかく、方針としては2問目3問目の方が迷ったかも。