同僚に「最近ARCのC,Dを毎日2問ずつぐらい解くようにしてるんだよね」という話をしたら,「何か難しい問題あった?」と聞かれた.(お前ら僕よりよっぽどレーティング高いやろ!)
しばらく考えて解法が思い浮かばなかったこの問題を教えた.ちなみに,問題を教えたときはACしていなかったので急いでACした.(WAを出しているコードでdoubleの誤差で死んでた)
概要
解法
とする.
全列挙をやろうとすると時間切れで死ぬ.しかも,1戦目の順位だけを変化させて,積がM以下になる組を個数を数え上げようとすると,setで既に使った順位を管理していないとうまく数え上げができない.
中学校で習った反比例のグラフを思い出すと,のグラフはまでは急激に減少するが,それ以降はかなり緩やかに減少することがわかる. つまり,1戦目の順位を以下で変化させている限り,2戦目の順位の重複を気にする必要はなさそう.その逆もまた然り.
したがって,解はぐらいになりそう.ただし,微妙に意地悪なケースがあって,
- が平方数のとき,先述の値から1をひかないといけない(について重複して数え上げを行っているため)
- のとき,さらに1をひかないといけない(高橋君の順位を使うことができないため)
また,は最大で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; }