ARC094 D : Worst Case(700)
作成日:2018.09.04
最終更新日:2018.09.04
問題概要
101010人が2回のコンテストに参加し、各コンテストでは相異なる順位がついた。
Q個のクエリ「2回のコンテストでAi,Bi位を取った人より、順位の積が小さい人の数の最大値を求めよ」に答えよ。
制約
1≤Q≤100
1≤Ai,Bi≤109
考え方
順位の積が小さい人はいずれかのコンテストでより小さい順位をとっていなければならない。
条件を満たす人数を最大化するために、両方のコンテストでそれぞれAi未満、Bi未満の順位をとった人がいないとする。
この時順位の積はできるだけ小さくしたいから、1回目のコンテストでの順位がAi未満であった人の中で条件を満たすのがn人である時、1回目のコンテストでは1位からn位、2回目のコンテストでは(Bi+1)位から(Bi+n)位をとったものとして良い。
またnを固定した時に順位の積の最大値を小さくしたいから、順位の組み合わせは[1,Bi+n],[2,Bi+n−1],...,[n,Bi+1]であるとして良い。
この時これらn人の2回のコンテストでの順位の和sは等しいから、順位の積の最大値はn<s/2の時n(Bi+1)、n≥s/2の時⌊s/2⌋⌈s/2⌉である。
s=Bi+n+1,n<Aiであるから、Ai≤Biであればnが最大値Ai−1をとる時もn<s/2,n(Bi+1)<AiBiである。
このことはコンテストの1回目と2回目(AiとBi)を入れ替えても成り立つことから、両方のコンテストでそれぞれAi未満、Bi未満の順位をとった人がいないとしても答えは変わらないことがわかる。
後はAi>Biの時に1回目のコンテストでの順位がAi未満出会った人の中で条件を満たす人数の最大値を求められれば良い。
先の考察よりnを決めれば順位の積の最大値が求まるので、nについての二分探索を行えばこれを求められる。
またAiBi≥(Bi+1)Biであるので、n<Biであれば確実に条件を満たし、n<s/2を満たすnの最大値Biにおいての順位の積の最大値はn≥s/2の時と同じになるから、⌊s/2⌋⌈s/2⌉とAiBiとだけを比較すれば良い。
以上によりクエリ当たりO(logmax(Ai,Bi))で求められるから十分高速である。
ソースコード
マクロ等はこちら
- 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;
- }
解法まとめ
Ai=Biならば答えは2(Ai−1)である。
そうでない時、⌊s/2⌋⌈s/2⌉<AiBiを満たす最大の整数sにおいてs−2(=Bi−1+n)が答えとなる。(1-5,11行)