Codeforces #281 Div2 C. Vasya and Basketball

CF281に参加。
ABCDをかなり速く解けたと思ってたら、Cで凡ミスして落としたせいで微妙な順位。
http://codeforces.com/contest/493/problem/C

問題

バスケの試合中、２つのチームがそれぞれN,M回シュートを入れた。
その時、リングからの距離はA[i],B[i]である。

距離dより遠い距離からシュートを入れると３点、d以下の距離だと２点入る。
前者のチームが、後者よりより多くの差をつけられる距離dを求め、その時の両者のスコアを求めよ。

解法

先にA,Bをソートしておく。
dの候補としてA[i]とB[i]のそれぞれとし、各dに対し両チームの得点を求めればよい。
lower_bound等を使うことで、3点入ったシュートの数を求めることができる。

コーナーケースとして、全部２点や全部３点のケースを漏らさないよう注意。

int N,M;
ll A[300000],B[300000];
set<ll> C;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], C.insert(A[i]);
	cin>>M;
	FOR(i,M) cin>>B[i], C.insert(B[i]);
	sort(A,A+N);
	sort(B,B+M);
	
	ll ta=2*N,tb=2*M;
	ITR(it,C) {
		int a=lower_bound(A,A+N,*it)-A;
		int b=lower_bound(B,B+M,*it)-B;
		
		ll ta2=N*3-a;
		ll tb2=M*3-b;
		if(ta2-tb2>ta-tb || (ta2-tb2==ta-tb && ta2>ta)) ta=ta2,tb=tb2;
	}
	_P("%lld:%lld\n",ta,tb);
	
}

まとめ

見事にコーナーケースを漏らした…。