競プロチャレンジ供養会場: AtCoder Beginner Contest 215 F - Dist Max 2

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1853 (記事作成時点)

供養

解法

• ある数 $K$ について、異なる2点の距離の最大値 $D$ が $K$ 以上であるかを考える
  • 2点 $i, j$ の距離が $K$ 以上であるということは $|x_{i} - x_{j}| \ge K$ かつ $|y_{i} - y_{j}| \ge K$ である
    • $(i, j)$ の組が存在するかの判定なので、$x_{i} \ge x_{j}$ を仮定してよい
  • ある点 $i$ について、$x_{j} \le x_{i} - K$ であるようなすべての $j$ のうち、$y_{j} \ge y_{i} + K$ もしくは $y_{j} \le y_{i} - K$ であるような $j$ が存在すれば $D \ge K$ である
  • 点を $x$ についてソートし、$i = 2, \dots$ について $x_{j} \le x_{i} - K$ であるような $j$ のうち $y_{j}$ の最大値と最小値をそれぞれ求め、$y_{i}$ との差が $K$ 以上か判定すればよい
    • $i = k$ のとき $i = k - 1$ のときの最大値と最小値を使って、$x_{j} = x_{i} - K$ であるような $j$ のみで最大値と最小値を更新すればよいので、$O(N)$ で判定可能
• $K$ について二部探索すれば答えが出る

実装

計算量は $x_{i}$ の最大値を $X$ として $O(N \log N + N \log X)$

公式解説

躓いた点

• 最大値と最小値だけ持っておけばいいということに気付かなかった