ARC094 D : Worst Case(700)
作成日：2018.09.04
最終更新日：2018.09.04
問題概要
$10^{10^{10}}$人が2回のコンテストに参加し、各コンテストでは相異なる順位がついた。
$Q$個のクエリ「2回のコンテストで$A_i$,$B_i$位を取った人より、順位の積が小さい人の数の最大値を求めよ」に答えよ。
制約
$1 \leq Q \leq 100$
$1 \leq A_i , B_i \leq 10^9$
考え方
順位の積が小さい人はいずれかのコンテストでより小さい順位をとっていなければならない。
条件を満たす人数を最大化するために、両方のコンテストでそれぞれ$A_i$未満、$B_i$未満の順位をとった人がいないとする。
この時順位の積はできるだけ小さくしたいから、1回目のコンテストでの順位が$A_i$未満であった人の中で条件を満たすのが$n$人である時、1回目のコンテストでは$1$位から$n$位、2回目のコンテストでは$(B_i+1)$位から$(B_i+n)$位をとったものとして良い。
また$n$を固定した時に順位の積の最大値を小さくしたいから、順位の組み合わせは$[1,B_i+n]$,$[2,B_i+n-1]$,...,$[n,B_i+1]$であるとして良い。
この時これら$n$人の2回のコンテストでの順位の和$s$は等しいから、順位の積の最大値は$n \lt s/2$の時$n(B_i+1)$、$n \geq s/2$の時$\lfloor s/2 \rfloor \lceil s/2 \rceil$である。
$s = B_i + n + 1$,$n \lt A_i$であるから、$A_i \leq B_i$であれば$n$が最大値$A_i - 1$をとる時も$n \lt s/2$,$n(B_i+1)$$\lt A_i B_i$である。
このことはコンテストの1回目と2回目($A_i$と$B_i$)を入れ替えても成り立つことから、両方のコンテストでそれぞれ$A_i$未満、$B_i$未満の順位をとった人がいないとしても答えは変わらないことがわかる。
後は$A_i \gt B_i$の時に1回目のコンテストでの順位が$A_i$未満出会った人の中で条件を満たす人数の最大値を求められれば良い。
先の考察より$n$を決めれば順位の積の最大値が求まるので、$n$についての二分探索を行えばこれを求められる。
また$A_i B_i$$\geq (B_i+1)B_i$であるので、$n \lt B_i$であれば確実に条件を満たし、$n \lt s/2$を満たす$n$の最大値$B_i$においての順位の積の最大値は$n \geq s/2$の時と同じになるから、$\lfloor s/2 \rfloor \lceil s/2 \rceil$と$A_i B_i$とだけを比較すれば良い。
以上によりクエリ当たり$O(log \: max(A_i,B_i))$で求められるから十分高速である。
ソースコード
マクロ等はこちら
LL BS(LL x , LL y , LL p){
if(y-x<2) return x;
LL z = (x+y)/2;
return (z/2) * ((z+1)/2) < p ? BS(z,y,p) : BS(x,z,p);
}
int main(){
int Q; cin >> Q;
repp(rep_t,0,Q){
LL A,B; cin >> A >> B;
cout << (A == B ? 2*(A-1) : BS(1,A+B+1,A*B)-2) << endl;
}
return 0;
}解法まとめ
$A_i = B_i$ならば答えは$2(A_i-1)$である。
そうでない時、$\lfloor s/2 \rfloor \lceil s/2 \rceil$$\lt A_i B_i$を満たす最大の整数$s$において$s-2$($= B_i - 1 + n$)が答えとなる。(1-5,11行)