ABC212C - Min Differenceを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 212 C - MinDifferenceを解いてみました。

まず問題文を見ます。

$A$と$B$の2つの数列から数値を選んだときの差の最小値を求める問題です。

同じ数値が両方に含まれていると、答えは$0$になります。

全探索すれば答えは出ますが、C問題ですし全探索では間に合わないでしょう。

次に制約を見ます。

$1 \le N, M \le 2 \times 10^5$なので、予想通り全探索$O(NM)$では間に合いません。

$O(N \log M)$なら間に合うので、二分探索が使えないか考えます。

まず、数列の並び順については何も記載されていないのでソートが必要になりますが、ソートの計算量は$O(N \log N)$なので、入力から読み込んだあとで1回だけソートすれば問題ありません。

次に、差の最小値については、$A$から選んだ値($A_i$)以上という条件で$B$を二分探索します。一致する数値があれば$0$が答えになり、そうでなければ$A_i$より小さい数値の最大値か、$A_i$より大きい数値の最小値のどちらかとの差が答えになります。

以上より、以下の手順で解きます。

1. $B$をソートする
2. $A$から数値を順番に選択し、$A_i$とする
3. $B$から$A_i$以上の値を二分探索で検索する
4. $A_i$未満の最大値と$A_i$との差の絶対値と、$A_i$以上の最小値と$A_i$との差の絶対値のより小さい方を記録する
5. 4で記録した数値の最小値を答えとする

Common Lispによる実装例

(let* ((n (read))
       (m (read))
       (a (make-array n :initial-contents (loop repeat n collect (read))))
       (b (make-array m :initial-contents (loop repeat m collect (read)))))

  (sort b #'<)

  (labels ((bsearch (ai &optional (l -1) (r m))
             (if (= (1+ l) r)
                 l
                 (let ((mid (+ l (floor (- r l) 2))))
                   (if (< (aref b mid) ai)
                       (bsearch ai mid r)
                       (bsearch ai l mid))))))

    (loop for ai across a
          for l = (bsearch ai)
          minimize (cond ((= l -1)
                          (abs (- (aref b 0) ai)))
                         ((= l (1- m))
                          (abs (- (aref b l) ai)))
                         (t
                          (min (abs (- (aref b l) ai))
                               (abs (- (aref b (1+ l)) ai)))))
            into it
          finally
             (format t "~A~%" it))))

二分探索の結果が$B$の両端になるときだけ少し注意が必要です。