codeFlyer C. 徒歩圏内
問題
N個の都市が直線上に並んでおり、それぞれの座標Xが与えられる。
都市iと都市jについて、2都市間の距離がD以下なら徒歩、そうでなければ電車で移動する。
このとき、都市の3つ組(i,j,k)で、以下を満たす個数を求めよ。
- i < j < k
- 都市iと都市jの間と、都市jと都市kの間は徒歩で移動
- 都市iと都市kの間は電車で移動
制約
- 3 <= N <= 10^5
- 0 <= X_i <= 10^9
- X_i < X_{i+1}
- 0 <= D <= 10^9
解法
条件の3番目だけ「i,k間の距離がDより大きいもの」になっていて、列挙が難しい。
そこで、条件の1番目と2番目を満たすものの中で、3番目の条件を反対にした「i,k間の距離がD以下のもの」を求めて、前者から除くことを考える。
条件の3番目を反対にした「i,k間の距離がD以下のもの」は、しゃくとり法の要領でO(N)で求めていける。
今、iから見てkが「距離D以下で一番遠いところ」だとして、この間の(k+1-i)個から2個選ぶと、その距離はD以下なので、(k+1-i)_C_2を足していけば求められる。
条件の1番目と2番目だけを満たすものは、同様に、しゃくとり法をしながら求めていける。
今、jから見てkが「距離D以下で一番遠いところ」だと計算していたとして、iから見てjが「距離D以下で一番遠いところ」となるようなiは、そのようなi,jのペアを(j,k)を求めるより前に求めているはずなので、memo[j] = iのようにメモして置く(しゃくとり法のs,tで言う所のtの更新whileの中で)。
そうすれば、条件を満たすものは、(j-i) * (k-i)なので、これを足していけば求められる。
どちらもO(N)で求められるので、全体の計算量はO(N)。
