Processing math: 100%

ARC094 D : Worst Case(700)

作成日:2018.09.04
最終更新日:2018.09.04

問題概要

問題本文

 101010人が2回のコンテストに参加し、各コンテストでは相異なる順位がついた。 Q個のクエリ「2回のコンテストでAi,Bi位を取った人より、順位の積が小さい人の数の最大値を求めよ」に答えよ。
制約
1Q100
1Ai,Bi109

考え方

 順位の積が小さい人はいずれかのコンテストでより小さい順位をとっていなければならない。 条件を満たす人数を最大化するために、両方のコンテストでそれぞれAi未満、Bi未満の順位をとった人がいないとする。 この時順位の積はできるだけ小さくしたいから、1回目のコンテストでの順位がAi未満であった人の中で条件を満たすのがn人である時、1回目のコンテストでは1位からn位、2回目のコンテストでは(Bi+1)位から(Bi+n)位をとったものとして良い。 またnを固定した時に順位の積の最大値を小さくしたいから、順位の組み合わせは[1,Bi+n],[2,Bi+n1],...,[n,Bi+1]であるとして良い。 この時これらn人の2回のコンテストでの順位の和sは等しいから、順位の積の最大値はn<s/2の時n(Bi+1)ns/2の時s/2s/2である。 s=Bi+n+1,n<Aiであるから、AiBiであればnが最大値Ai1をとる時もn<s/2,n(Bi+1)<AiBiである。 このことはコンテストの1回目と2回目(AiBi)を入れ替えても成り立つことから、両方のコンテストでそれぞれAi未満、Bi未満の順位をとった人がいないとしても答えは変わらないことがわかる。
 後はAi>Biの時に1回目のコンテストでの順位がAi未満出会った人の中で条件を満たす人数の最大値を求められれば良い。 先の考察よりnを決めれば順位の積の最大値が求まるので、nについての二分探索を行えばこれを求められる。 またAiBi(Bi+1)Biであるので、n<Biであれば確実に条件を満たし、n<s/2を満たすnの最大値Biにおいての順位の積の最大値はns/2の時と同じになるから、s/2s/2AiBiとだけを比較すれば良い。 以上によりクエリ当たりO(logmax(Ai,Bi))で求められるから十分高速である。

ソースコード

マクロ等はこちら

  1. LL BS(LL x , LL y , LL p){
  2. if(y-x<2) return x;
  3. LL z = (x+y)/2;
  4. return (z/2) * ((z+1)/2) < p ? BS(z,y,p) : BS(x,z,p);
  5. }
  6.  
  7. int main(){
  8. int Q; cin >> Q;
  9. repp(rep_t,0,Q){
  10. LL A,B; cin >> A >> B;
  11. cout << (A == B ? 2*(A-1) : BS(1,A+B+1,A*B)-2) << endl;
  12. }
  13. return 0;
  14. }

解法まとめ

 Ai=Biならば答えは2(Ai1)である。 そうでない時、s/2s/2<AiBiを満たす最大の整数sにおいてs2(=Bi1+n)が答えとなる。(1-5,11行)

ARC094の他の問題 C E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら