[AtCoder] ABC 119 D – Lazy Faith

Lazy Faith

https://atcoder.jp/contests/abc119/tasks/abc119_d

考え方

題意

神社と寺に訪れるために必要な最小の距離を答えます。

方針

神社と寺の位置の配列はソートされているので、ある地点 \( x_i \) 以上の一番近い神社と寺の位置は二分探索によって求めることができます。しかし、配列の最小値より小さい値や、最大値より大きい値が \( x_i \) に含まれることを考える必要があります。このような場合、番兵を用いて配列を構成すればよいです。実際には、\( s, t\) の先頭に \( -10^{11} \) 、末尾に \( 10^{11} \) を追加します。

あるクエリを \( x = x_j \) とします。\( x \leq s_i \) を満たす最小の \( i \) を \( a \) とし、\( x \leq t_i \) を満たす最小の \( i \) を \( b \) とします。これらは二分探索によって見つけることができます。番兵があるので、\( a , b\neq 0 \) となることに注意すると、以下の不等式が成り立つことが分かります。

\[ s_{a – 1} < x \leq s_a\]

\[t_{b – 1} < x  \leq t_b\]

求める距離は次の \( 2 \) パターンを考えます。

\( x \) から出発して \( x \) もう一度訪れるとき

このとき以下の \( 4 \) 通りが考えられます。

  • \(x\) -> \(s_a\) -> \(x\) -> \(t_{b-1}\)
  • \(x\) -> \(s_{a – 1}\) -> \(x\) -> \(t_{b}\)
  • \(x\) -> \(t_b\) -> \(x\) -> \(s_{b-1}\)
  • \(x\) -> \(t_{b-1}\) -> \(x\) -> \(s_{a}\)

\( x \) に訪れないとき

このとき以下の \( 2 \) 通りが考えられます。

  • \(x\) -> \( \max (s_a, \ t_b)\)
  • \(x\) -> \( \min (s_{a – 1},\  t_{b – 1})\)

上記の \( 6 \) 通りについて最小値を求めれば良いです。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする