codeFlyer C問題 徒歩圏内

解けなくて悔しいので記事に。考察の流れとかも書いておく。
排反をとるというのがtwitterで見ててわかりやすそうだったので実装。

bitflyer2018-qual.contest.atcoder.jp


考察した(ダメ)解法
1.  O(N^2 \log N ) : 左端と真ん中を決めて右端の数を二分探索で数える。左端と真ん中の決め方をしゃくとりできるかなと思ったが無理。{}_n C _2通り試さないとだめ。当然TLE。

2. 左端と右端を決めて、真ん中を二分探索で数える。1と本質的には変わらず。

二分探索と累積和を使う O(N \log N) 解法
正しい解法
左端の都市、真ん中の都市、右端の都市のindexをそれぞれ  i , j , k ( i < j < k ) と書く。
全ての  ( i , j , k ) の組み合わせは、 {}_n C _3 通り
ここから条件に合わないものを引くことを考える。

左端の都市  i を順に見ていく。

1.  (X_j - X_i) > D の場合 ->  {}_(X_iから右にDより離れている都市数) C _2 通り
真ん中が左端からDより離れている場合、右端も左端からDより離れている。
よって、(左端から右にDより離れている都市) の中から2つ選ぶ組み合わせに対応する。

2.  (X_ j - X_i ) \leqq D かつ ( X_k - X_j ) > D の場合 ->  \sum_{j}{} ( X_j から右にDより離れている都市数)
真ん中は左端からD以内だが、右端が真ん中から D以上離れている。
真ん中を決めうちし、右端の候補数を足し合わせたい。

3.  (X_k - X_i ) \leqq D の場合 ->  {}_(X_iから右にD以内にある都市数) C _2 通り
左端と右端がD以内の距離にある場合。この時、真ん中の点もD以内にある。
よって、(左端から右にD以内の都市) の中から2つ選ぶ組み合わせに対応する。

1,2,3で全ての場合を尽くしているので、これを全ての i に対して合計して、最後全体から引けば良い。

ここで、1,2で何度も  ( Dより離れている都市数 ) を使っており、2ではこれの累積値を取っていることから、
あらかじめ累積和を取っておくと2がスムーズに計算できそう。
各都市に対して、右にD以上離れている最小のindexの都市を二分探索で求める。
-> 累積和をとる。累積前も取っておくといいかな (?)

3の  (D以内の都市数) (Dより離れている都市数) から簡単に求まるので心配なし。

ソースコード
Submission #2603957 - codeFlyer (bitFlyer Programming Contest) | AtCoder