Mister雑記

競プロやります。

ARC094-D 「Worst Case」 (700) 別解

この解法を思いついたおかげでこの問題が好きになった。

問題リンク

概要

 10^{10^{10}}人が2回のコンテストに参加し、各参加者に独立な順位がつけられた。コンテストのスコアは2回のコンテストの順位の積によって定義される。

このとき、以下のような Q回のクエリに答えよ。

  •  i番目のクエリは整数 A_i B_iからなる。
  • 各コンテストで A_i位、 B_i位をとった高橋くんよりスコアが小さい参加者数の最大値を求めよ。

制約

  •  1 \leq Q \leq 100
  •  1 \leq A_i, B_i \leq 10^9

解説

タイトルにある通り、本記事ではeditorialとは少し異なる解法について解説する。

この解法は本記事を書いてる最中に思いついたもので、 「計算量を犠牲にして場合分けを減らした」といった趣旨の解法である。 逆にこの解法を数学によって計算量を減らそうとするとeditorialの解法になる。

解の上限

以降、対称性から A \leq Bとしておく。

高橋くんより小さいスコアを取るには、1回目のコンテストで A位未満を取るか、2回目のコンテストで B位未満を取らなければいけないことは明らかである。 すなわち解の上限は A + B - 2となる。

これだけの組数を作るとしたとき、最善なマッチングは以下のようになる。できるだけ大きい値とできるだけ小さい値同士をマッチングさせている。

f:id:misteer:20180919054104p:plain

f:id:misteer:20180919040946p:plain

前半については全部の組が条件を満たしている。これは、

 \displaystyle (A - i)(B + i) - AB = (A - B)i - i^2 \lt 0 (\because i \gt 0, A \lt B)

から分かる。

一方で後半は大半の場合で (B, A)を含め積が AB以上となる組が存在するため、このマッチングは成立しない。

解で二分探索

ここで、「 A + K - 2組作ることが可能か?」という問題について考えてみる。 この問題は Kについて明らかに単調性が成り立つため、二分探索によって最大の Kを求めることができる。

先の B Kに変えて、 A + K - 2組作る場合の最適なマッチングについて考えると以下のようになる。

f:id:misteer:20180919054104p:plain

f:id:misteer:20180919041007p:plain

後者の各組は (A + K - i, K + i)と表せるので、  (A + K + i)(K - i) 0 \leq i \lt Kにおける最大値が AB未満ならこのマッチングは成立することになる。

どの辺で最大値を取るか?

しかし全ての 0 \leq i \lt Kについてチマチマ (A + K + i)(K - i)を調べていると当然ながらTLEとなる。

それでは上の値を iについての二次関数とみて、数学的に最大値を求めるか? これをやって沼にハマったのが私で、残念ながらこのアプローチで解を求めるのは厳しい。

実はどの辺で最大値を取るかってのはそんな面倒なことをしなくても分かり、答えは「 A + K - i \fallingdotseq K - iのとき」となる。 これは (a + b)(a - b) = a^2 - b^2 \lt a^2からなんとなく分かるだろうか。

各組は値の和が A + Kであることから、 m = \lceil (A + K) / 2 \rceilとおくと (m, A + K - m)は最も真ん中に近い組となる。 したがって m (A + K - m) ABの大小を比較するだけで、上の可能性問題は解けてしまう!

ただし1つだけコーナーケースが存在する。それは A = Kのときで、このときは実際に (A, A)の組を取ることがないため m = A - 1とする必要がある。そもそもOKの判定にしてしまっても問題ない。

実装例

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        ll A, B;
        cin >> A >> B;
        if (A > B) {
            swap(A, B);
        }  // A <= B

        ll ok = A, ng = B + 1;
        // K = Aのときは前半と同様にマッチングすればいい
        
        while (ng - ok > 1) {
            ll K = (ok + ng) / 2;
            ll m = (K + A) / 2;
            
            // コーナーケース
            if (K == A) --m;
            
            if (m * (A + K - m) < A * B) {
                ok = K;
            } else {
                ng = K;
            }
        }
        cout << ok + A - 2 << endl;
    }
    return 0;
}

感想

  • 個人的にこの解法には大いに満足している。
    • といっても他にもこの解法で解いた人はたくさんいそうだが。
  • 解説記事を書こうとすると「できるだけ書くのが楽で納得しやすい説明にしたいな〜」という思考になるためこの解法が生まれた。解説記事様々である。
    • みんなも解説記事、書こう!