C - 徒歩圏内

Quiz

https://atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c

Submit

https://atcoder.jp/contests/bitflyer2018-qual/submissions/4634379

Note

気づき

  • 条件の変形
  • i, j, k 真ん中固定
  • 単調性
    • 二分探索
    • しゃくとり法

解法

  • 中央 j を全探索(固定)しつつ、jから左右に距離D以内で何個あるかを二分探索で数える
    • ここで、jごとに余分なものを除去したい気になるが抑えて、いったんjを動かして合計を求める
  • あとは余分な(i, j, k)を引いていけばいい
  • 今度は左端 i を全探索(固定)しつつ、iから右に距離D以内のものを数える。nとする
    • その中から2個選び、順に j, kと名づければいい
    • それを除去するので、nC2を引けばいい