AtCoder ARC #094 : D - Worst Case

うーん、微妙な出来。
https://beta.atcoder.jp/contests/arc094/tasks/arc094_b

問題

多くの人がコンテストに参加し、２問の問題を解いた。
それぞれの問題で、同着なく１位から順位が着く。
参加者のスコアは、２回の順位の積である。

２回のコンテストの順位がA,Bだった人がいた場合、それよりスコアの低い人は最大何人いるか。

解法

A≦Bとする。
1問目で1～(A-1)位だった人は２問目で(B+A-1)～(B+1)位を取ると全員問題の人より低いスコアになる。
(１問目がA-x、２問目をB+xとするとスコアがAB+(B-A)*x-x*x＜AB）
また、２問目で1～(A-1)位だった人も同様に1問目で(A+B-1)～(B+1)位を取ると全員問題の人より低いスコアになる。
この時点で2*(A-1)人いるのが確定である。

残りは１問目の順位が(A+1)～B位で２問目の順位がA～(B-1)位の組み合わせが可能性として残っている。
二分探索でこのうち題意を満たす人数xを求めよう。
1問目が(A+1)～(A+x)の人が対応して2問目が(A+x-1)～A位を取るようにしたとき、全員スコアがAB未満となるxの最大値を求める。
実際にはxに対し全員AB以下かチェックする必要はなく、中心付近だけでよい。

int Q;
ll A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>A>>B;
		if(A>B) swap(A,B);
		ll ret=2*(A-1);
		
		int num=0;
		for(i=29;i>=0;i--) {
			num+=1<<i;
			if(A+num>B) {
				num-=1<<i;
				continue;
			}
			int ng=0;
			for(x=num/2-2;x<=num/2+2;x++) {
				if(x<=0 || x>num) continue;
				if((A+x)*(A+num-x)>=A*B) ng=1;
			}
			if(ng) num-=1<<i;
		}
		ret+=num;
		
		cout<<ret<<endl;
	}
}

まとめ

なんか妙に手間取った。