Min Difference [AtCoder Beginner Contest 212 C]

https://atcoder.jp/contests/abc212/tasks/abc212_c

前提知識

• 二分探索, lower_bound

解説

https://atcoder.jp/contests/abc212/submissions/24696602

想定解法とは異なる解法ですが、達成したい目標は同じで、より高速化した解法が想定解法となります。
二分探索、それかlower_boundについて理解できていることを前提として書きます。

まずは全探索を考えてみる

愚直に解いていくことを考えると、iとjを全探索して、abs(A[i] - B[j])の最小値を取れば答えになる。
こうすると、全組合せ数は4*10¹⁰通りとなるので、間に合わない。
なお、間に合う目安は10⁷通りくらいである。
この解法はオーダー記法にするとO(N²)なので、高速化していく必要がある。

高速化方針

このような2要素を全探索する解法の高速化の方針として、1つの要素は全探索で、もう片方を最適化するというものがある。
今回はこれが適用でき、iは全探索することにして、jの選択を最適化していくことにしよう。

iを全探索するので、A[i]が分かっているときにより最適なj、ないし、B[j]はどういうものかを考える。
絶対値が最も小さくなるのが最適なものなので、B[j]はA[i]に最も違いものが高速に取り出せれば良い。

配列Bの中でA[i]に最も近いものは？

この問題を解決するのに、二分探索、それを内部で使っているlower_bound関数を利用する。
C++にある関数であるが、以下のような機能を持つ。

lower_bound(begin, end, x) := ソート済み配列の[begin,end)の範囲でx以上となる最小の要素のイテレーションを返す

C++にしかなく、イテレーションとは？という話はあると思うが、ざっくり添え字と考えた場合は以下のような動きになる。

1 2 3 4 5 6  
===========  
2 4 5 7 7 9  
  
lower_bound(1, 6, 5) = 3  
lower_bound(1, 6, 6) = 4  
lower_bound(1, 6, 7) = 4  

こんな感じ。この検索は内部的に二分探索が使われているので計算量はO(logN)となる。
注意として、オーダー記法になじみが無い場合は、大体logN回くらいの検索回数になっていると思っておこう。
使われる配列はソート済みである必要があるので、配列Bはソートしておこう。
（この時にソートしても答えに影響ないことを確認すること。今回はない）

さて、lower_boundで検索する数をA[i]にすれば、A[i]以上で最小の要素が何かが高速に分かる。
A[i]以上で最小の要素が得られたら、それよりも大きい数は絶対値は離れていくはずなので考慮する必要はない。
だが、A[i]未満で絶対値が最小の数が存在するかもしれない。
なので、得られた要素の1個前の要素も答えの候補となるので、それも計算してあげよう。

このようにしてやるとjの候補は2通りに絞られる（かつ、絞る計算も早い）ので、以前のM通りに比べて大量に候補を減らすことができ、間に合う。

int N, M, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    sort(A, A + N);
    sort(B, B + M);

    int ans = inf;
    rep(i, 0, N) {
        int j = lower_bound(B, B + M, A[i]) - B;
        if (j < M) chmin(ans, abs(A[i] - B[j]));
        if (0 <= j - 1) chmin(ans, abs(A[i] - B[j - 1]));
    }
    cout << ans << endl;
}