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 - i² < 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;
        }

ポイント

• 最適な組み合わせを考える

類題