🦁

lower_bound ABC212 C Min Differenceを理解し忘れないようにする。

2024/08/04に公開

片方を固定して、もう一方を2分探索で求める典型考察
lower_boundの仕様
- 配列bからa_iを探索する場合,b_i以上の最小値を求める
- 探索した値の要素番号を見つける場合は、b.begin()を引く。
- 探索するa_iがb.back()より大きい場合、要素番号はb.back()となり、これをそのままbに当てると当然配列外参照になる。
めぐる式2分探索を使うと、lower_boundと同様に境界値がバグらずに求められるみたい(詳細なキャッチアップはまだ)

a_i,b_iをそれぞれの引き算の絶対値を計算した際に最小値を求める問題

入力例1

2 2
1 6
4 9

出力例1

入力例1の場合、|1-4|=3,|1-9|=8,|6-4|=2,|6-9|=3
よって答えは|6-4|の2となる。

a_iに最も値が近いb_iをそれぞれ求めてその最小値を出すといけると思ったが、それをするとO(NM)になる。

a_i,b_iどちらか片方を固定して、もう片方と一番近い値を求める方針は間違ってなかった。
その近い値の求め方は2分探索を用いるとO(NlogM)でO(NM)にならずにすむ
今回はa_iを固定するのでb_iをソートし2分探索してa_iと一番近い値を求める。

入力1なら

2 2
1 6
4 9

1と近いのは4で|1-4|=3,6と近いのは4で|6-4|=2、よってmin(3,2)=2が答えとなる。

2分探索はlower_boundを用いて実装した。ただこれだと問題があり、lower_boundはa_i以上の値を取得する。

よって下記のようなコードだと

rep(i,n) {
    int d = *lower_bound(all(b),a[i]);// a_iが6の場合、9がdに入る
  }

a_iが6の場合、もっとも値が近い4を取得したいのに、6以上の9を取得してしまう問題が発生した。これをどうするか。。

方法として、lower_boundは探索したい数値以上の値が現れる最初の位置を配列から取得するので
探索結果の以上の値が現れる最初の位置のイテレータとその一つ前の位置のイテレータを比較すればいいことが分かる。
a_iが6の場合、9と一つ前の4を計算し最小値を求めればいい。

ただこのやり方だとコーナーケースが２点発生するので対応する必要がある。
１点目、探索結果のindexが0の場合は、配列外参照になる。
２点目、a_i > b.back()の場合、lower_boundで取得するindexはb.size()になり配列外参照になる。

解説放送では、どちらもソートして小さい方にカーソルを移動させる解き方を行っていたが典型アルゴリズムが使われておらず記憶に残りそうにない。。

めぐる式2分探索を使うと、バグらずにrightにlower_boundの返り値と同様の値が入るそう。
よってその返り値でa_i以上の値の最小値のindexを求められるので、その境界値で計算を行えばいい。
下記記事が分かりやすかった。深掘りは後ほど