ABC093-D:Worst Case
問題
https://beta.atcoder.jp/contests/abc093/tasks/arc094_b
[1, 10^(10^10)] の参加者がいるプログラミングコンテストがある。高橋君は1回目で A 、2回目で B 位になった。参加者のスコアは 2回のコンテストの順位の積で与えられる。高橋君よりもスコアの小さい参加者の人数を求めよ。
考え方
最大のペアを作るマッチング問題である。
A <= B としておく。
1回目で A よりも小さい A - i の順位をとる場合、2回目で B - i の順位にすることで
(A - i) * (B - i) = AB + (A-B)i - i2 < AB
高橋君よりも小さなスコアにすることができる。これは A - 1 人のペアを作ることができる。
1回目で B よりも小さい B- i の順位をとった場合は、上記と同じ議論はできない。AB を超えるペアができるため。
いま、全部で K ペア作ることができると仮定しよう。そのときペアとなる数は以下のようになっているはずである。
K つのペアをとるとき、最大値が AB を超えなければ K ペア作ることができる。そうでないときは K ペア作ることはできない。これは単調性が成立する。
後は K ペア作るときの最大値が AB を超えないか確かめる必要がある。[1, A-1], [A+1,K+1] と [K+1, B+1], [B-1,1] についてはほぼ単調数列になっていて、このペアの最大値は数列の真ん中あたりになる。三分探索で求めることもできるが、真ん中あたりのペアの最大値が AB を超えないか確認すれば良い。
public void solve(int testNumber, InputReader in, PrintWriter out) { int q = in.nextInt(); while (q-- > 0) { long a = in.nextLong(), b = in.nextLong(); out.println(calc(a, b)); } } long calc(long a, long b) { if (a == b) return (a-1) * 2; long limit = a * b - 1; long l = min(a, b) - 1, r = max(a, b) * 2 - 1; while (r - l > 1) { long k = (r+l)/2; long max = 0; for (long i = max(k/2-100, 1); i < k/2+100; i++) { max = max(max, i * (k + 1 - i)); } if (max > limit) { r = k; } else { l = k; } } return l - 1; }
ポイント
- 最適な組み合わせを考える