codeFlyer 2018 予選 C - 徒歩圏内

• 問題

問題概要

昇順に並んでいる数列{x_i} (1<=i<=N) が与えられる.
(i, j, k) , (i < j < k) の組で,
x_j - x_i <= D
x_k - x_j <= D x_k - x_i > D
を満たす組の総数を求めよ. 3 <= N <= 10⁵

解法

補集合を考える.
x_j - x_i <= D, x_k - x_j <= D を満たす(i, j, k)の組から
x_j - x_i <= D, x_k - x_j <= D, x_k - x_i <= D を満たす(i, j, k)の組を引けばよい.
前者は j を動かして min(i)とmax(k)を二分探索で出し,
後者は i を動かして max(k)を二分探索で出し, iとkの範囲から二つ取ってくる組み合わせを足して行けば良い.

メモ

解けなかった..
条件がややこしくて高速に求められなかったら補集合を考えよう.

コード