ARC094 D: Worst Case

同僚に「最近ARCのC,Dを毎日2問ずつぐらい解くようにしてるんだよね」という話をしたら,「何か難しい問題あった?」と聞かれた.(お前ら僕よりよっぽどレーティング高いやろ!)

しばらく考えて解法が思い浮かばなかったこの問題を教えた.ちなみに,問題を教えたときはACしていなかったので急いでACした.(WAを出しているコードでdoubleの誤差で死んでた)

概要

D - Worst Case

解法

M=AB-1とする.

全列挙をやろうとすると時間切れで死ぬ.しかも,1戦目の順位だけを変化させて,積がM以下になる組を個数を数え上げようとすると,setで既に使った順位を管理していないとうまく数え上げができない.

中学校で習った反比例のグラフを思い出すと,y=M/xのグラフは\sqrt{M}までは急激に減少するが,それ以降はかなり緩やかに減少することがわかる. つまり,1戦目の順位を\sqrt{M}以下で変化させている限り,2戦目の順位の重複を気にする必要はなさそう.その逆もまた然り.

したがって,解は2\lfloor\sqrt{M}\rfloorぐらいになりそう.ただし,微妙に意地悪なケースがあって,

  • Mが平方数のとき,先述の値から1をひかないといけない(\sqrt{M}について重複して数え上げを行っているため)
  •  min(A,B) \le \sqrt{M} のとき,さらに1をひかないといけない(高橋君の順位を使うことができないため)

また,Mは最大で18桁ぐらいになるので,doubleのsqrtだと精度が足りなくなるので,自前で平方関数を作る必要がある.

#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

int sqrtb(int a) {
    int l = 1, u = (int)2e+9;
    while(u - l > 1) {
        int c = (l + u) / 2;
        if (c * c <= a) {
            l = c;
        } else {
            u = c;
        }
    }
    return l;
}

signed main(){
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; ++i) {
        int A, B;
        cin >> A >> B;
        if(A > B) swap(A,B);
        if(B == 1) {
            cout << 0 << endl;
            continue;
        }
        int M = A * B - 1;
        int L = (int)sqrtb(M);
        int t = 2 * L - (M / L == L);
        if(A <= L) {
            --t;
        }
        cout << t << endl;
    }
    return 0;
}