codeFlyer-C 徒歩圏内
概要
数直線上にN個(N <= 10^5)の点があり、それぞれの座標は[1, 10^9]
にあり、昇順で与えられる。
で、を満たすの組み合わせの数を求めよ。
ACするまで
1. 条件の緩いものから求める!この問題の場合は、いろいろ考え方はあるが、よりも、かつの方が扱いやすい!
2. しかし、1の場合、のものまで含むので除外しないといけない。
3. それぞれ簡単な二項係数や掛け算で終わる。(DEGwer風)
考察
数学的な数え上げに限らず、数え上げは
条件が簡単なものから扱う!そして、行き詰ったら別の方法(固定するものを変える)でトライ!
今回の場合は、は余事象を使えば求まるものの、その中からまたかつを選び出すのは容易ではない。ここは一旦切り替える。
今度は3つ選ぶという条件に着目する。コンテストでよく見る3つについての選択などは、
真ん中固定→左右を独立して考える
左or右固定→もう一端を二分探索
というものが見られる。
今回は、かつという条件を使ってみると、これは先ほどの真ん中固定と同じになるとわかる。
そして、二分探索でそれぞれを中心としたときに許容される区間の左端、右端がわかる。それぞれの区間の長さの積を集計すればよい。
この時、を除かねばならないが、これは先ほどの左or右固定の考え方でその場合の数が分かる。
左端を決めた時、右端の限界がわかる。そして、その限界までの間に(j, k)を二つ置けばよい。
よって、で一つ目の集計がわかり、で二つ目の集計ができるので、この問題はでできた。
ちなみに、この問題でも、二分探索を尺取法におきかえればO(N)の時間でとける。
最後に
さんざん見た形なのでとけないといけない。