Quiz
https://atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c
Submit
https://atcoder.jp/contests/bitflyer2018-qual/submissions/4634379
Note
- 解法はアルメリアさんのが詳しい https://betrue12.hateblo.jp/entry/2018/06/03/131350
気づき
- 条件の変形
- i, j, k 真ん中固定
- 単調性
- 二分探索
- しゃくとり法
解法
- 中央 j を全探索(固定)しつつ、jから左右に距離D以内で何個あるかを二分探索で数える
- ここで、jごとに余分なものを除去したい気になるが抑えて、いったんjを動かして合計を求める
- あとは余分な(i, j, k)を引いていけばいい
- 今度は左端 i を全探索(固定)しつつ、iから右に距離D以内のものを数える。nとする
- その中から2個選び、順に j, kと名づければいい
- それを除去するので、nC2を引けばいい