codeFlyer （bitFlyer Programming Contest）オープンコンテスト：B - 交通費

問題

https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b

考え方

各クエリに O(logN) で答える必要がある。

交通費の条件に着目すると、 |X_i - c| \leq d のとき |x_i - c| 円であり、そうでない場合は d 円であることから区間 [c-d,c+d] に含まれる値の個数を求めたい。絶対値で場合分けして、c の右側の区間 [c,c+d] と左側の区間 [c-d,c) に含まれる個数を求める。

数直線上のある数以下の個数、ある数未満の個数は二分探索で求めることができる。区間の右側に含まれる個数を cnt_r 左側に含まれる個数を cnt_l 、それ以外の個数を m=n-cnt_r-cnt_l とすると求める解は

(\sum X_i - cnt_r * c) + (cnt_l * c - \sum X_i) + m * d

である。

Submission #4142816 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

どこに着目して考察するべきだったか

区間の個数を二分探索で求める気持ちになると解ける。

何がバグっていたか

得た知見(典型ポイント)

  • 区間に含まれる個数を二分探索で求める
  • 絶対値を外すように場合分け

類題