Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

codeFlyer-C 徒歩圏内

atcoder.jp

概要

数直線上にN個(N <= 10^5)の点があり、それぞれの座標は[1, 10^9]
にあり、昇順で与えられる。
 1 <= i < j < k <= Nで、 X_k - X_i >D and X_j - X_i <=D , X_k - X_j <= Dを満たす (i, j, k)の組み合わせの数を求めよ。

ACするまで


1. 条件の緩いものから求める!この問題の場合は、いろいろ考え方はあるが、 X_k - X_i > Dよりも、 X_j - X_i <= Dかつ X_k - X_j <= Dの方が扱いやすい!
2. しかし、1の場合、 X_k - X_i <= Dのものまで含むので除外しないといけない。
3. それぞれ簡単な二項係数や掛け算で終わる。(DEGwer風)

考察

数学的な数え上げに限らず、数え上げは

条件が簡単なものから扱う!そして、行き詰ったら別の方法(固定するものを変える)でトライ!

今回の場合は、 X_j - X_i > Dは余事象を使えば求まるものの、その中からまた X_j - X_i <= Dかつ X_k - X_j <= Dを選び出すのは容易ではない。ここは一旦切り替える。

今度は3つ選ぶという条件に着目する。コンテストでよく見る3つについての選択などは、

真ん中固定→左右を独立して考える
左or右固定→もう一端を二分探索

というものが見られる。
今回は、 X_j - X_i <= Dかつ X_k - X_j <= Dという条件を使ってみると、これは先ほどの真ん中固定と同じになるとわかる。
そして、二分探索でそれぞれを中心としたときに許容される区間の左端、右端がわかる。それぞれの区間の長さの積を集計すればよい。

この時、 X_k - X_i <= Dを除かねばならないが、これは先ほどの左or右固定の考え方でその場合の数が分かる。
左端を決めた時、右端の限界がわかる。そして、その限界までの間に(j, k)を二つ置けばよい。

よって、 O(N log N)で一つ目の集計がわかり、 O(N)で二つ目の集計ができるので、この問題は O(N log N)でできた。

ちなみに、この問題でも、二分探索を尺取法におきかえればO(N)の時間でとける。

最後に

さんざん見た形なのでとけないといけない。