TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

11 /
23
2021
 

Range Point Distance

問題

B – Range Point Distance
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

ポイント

  1. \(dist(l, r, x)\) は \(max(0, l – x, x – r)\) といえる。
  2. 1.をまとめると \(max(0, L_1 – x, x – R_1, L_2 – x, x – R_2,…L_N – x, x – R_N)\)。
  3. \(L\) に注目すると採用される可能性があるのは、 \(L_a = max(L_1,L_2,…L_N)\)。
  4. \(R\) に注目すると採用される可能性があるのは、 \(R_a = min(R_1,R_2,…R_N)\)。
  5. 3.と4.より2.は \(max(0, L_a – x, x – R_a)\)と言い換えることができる。
  6. \(L_a <= R_a\) のときは 5.の答えを \(0\) にすべきなので、 \(x = L_a\)。
  7. \(L_a > R_a\) のときは 5.の答えを \(ceil((L_a – R_b)/2)\) にすべきなので、 \(x = floor((L_a + R_a)/2)\)。
  8. 上記3.4.6.7.を \(1,2,…N\) まで計算する。