codeFlyer C問題徒歩圏内 - banbooooのブログ

解けなくて悔しいので記事に。考察の流れとかも書いておく。
排反をとるというのが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