ARC094 D. Worst Case - phyllo’s algorithm note

問題

10^10^10人の参加者が2回のプログラミングコンテストに参加し、高橋くんも2回参加し、1回目にA位、2回目にB位だった。
参加者のスコアが2回の順位それぞれを掛け合わせた値であるとき、高橋くんよりスコアの小さい参加者は最大何人いるか、答えよ。

制約

A,BのペアはQ個与えられ、それぞれ答える
1 <= A, B <= 10^9
入力は全て整数

解法

本番は、なんとなく約数かと思って時間を潰したけど、スコアがA*B未満であれば良いので、できるだけ小さいもの同士を掛け合わせた方がよい、ことに気づく必要がある。
想定解法は場合分けのようだけど、「高橋くんよりスコアの小さい参加者がX人」というのがありえるかどうか？を求められれば、2分探索で求められてわかりやすいので、これを考える。

コンテストの1回目の方の順位では1,2,3,...と小さい方から順位AをのぞいたX個分の順位を使った方が、できるだけ掛け算したときの値を小さくできるので、これを使うことを考える。
コンテストの2回目の方の順位でも、同様に考えると、1,2,3,...と小さい方から順位BをのぞいたX個分の順位を使った方が、掛け算した時の値を小さくできる。

どちらの順位も1,2,3,...となっている場合に、どのようにペアを作れば、掛け算した時の最大値が小さくできるか？
これは、片方を逆にして掛け合わせるのがよい。

A=3, B=5, X=5
1回目: 1 2 4 5 6
2回目: 6 4 3 2 1

掛け合わせると、6,8,12,10,6なので、最大値は12。A*B=15未満なので、X=5はありえる。

最大値になっているところがx*yだった場合、それをより小さくするため、別のペアになるよういじると、x*(y+1)にペアを変えればより大きくなってしまうし、x*(y-1)にすると、yとペアになるのは(x-1)以下でないといけなくなるが、それを繰り返すと残るのが最大順位同士になってx*yより悪化することになる。(A,Bで抜けている部分があっても同様)

ということで、各コンテストで1,2,3,...でA,BをそれぞれのぞいたX個分の順位を使って、昇順、降順の値の掛け合わせで最大値の部分がA*B未満であればXペア作れて、「高橋くんよりスコアの小さい参加者がX人」はありえる、と判断できる。

この「最大値の部分」を求める方法は、

中心付近が最大値になるので、中心付近を10個ぐらい確認して最大値を見つける
部分的に等差数列なので、一般項は「a_i = a_0 + i」と「b_i = b_0 - i」ですぐわかり、それの掛け算になるので、最大になるiを掛け算したものをiについて求めて得る
上に凸なので、配列の3分探索で求める

などが考えられる。
配列の3分探索は、隣との差分(微分)が+,+,+,0,0,0,-,-,-のようになるので、「0以上と-の境界」を2分探索で求めてあげればよい。

また、2分探索時に、Xがある程度大きいところ(例えばrb=A*Bとか)まで探索する場合、「最大値の部分」が64bitを超えてしまう可能性があるので、注意。