AtCoder Regular Contest 068：E - Snuke Line
問題
https://atcoder.jp/contests/arc068/tasks/arc068_c
考え方
これは難しい...
考えていたこと
- imos法で区間を含むか数える、がこれは重複して数えてしまうのでダメ。
を全通り試すことは
でできるのでこれは全探索
解説見た
公式解説のベースに考えていく。がほぼまんま公式解説の写しみたいになってしまった...
今区間の長さ について考えていることにする。
なる
番目の区間について区間の長さが
よりも大きい
場合は必ず
回以上は訪れることになる。そうでないとき、つまり
であるときは高々1回のみ訪れることになる。
上記から区間の長さ で分類して考えることができて、これが重要な考察である。区間の長さが小さい区間から考えていく。これは各区間について区間の長さで昇順ソートすればよい。
駅 に含まれる種類の数を
で表すことにする。
区間の長さが の区間
について
を満たしているとき
なる
に
を加算する。これは BIT などのデータ構造を用いればよい。(区間加算できるように imos 法のような工夫が必要)
このとき が区間の長さが
未満の区間に含まれる種類の合計となる。これに、区間の長さが
以上の区間の個数を足せばよい。
長さ 未満の区間の数について、区間の長さ
で含まれる場合は
でも必ず含まれるので、それぞれの区間については
回見ればよいことがわかる。区間の長さ
でどこまでの区間まで計算したか保持しておけばよい。
よって全体の計算量は となる。
ちなみに で全探索しても
になるのは、区間の個数は
個であるため。調和級数を近似すると
で抑えられるというテク。
ちなみに放送解説も見たが、xy平面の個数をO(logM)で数える手法が難しかった
どこに着目して考察するべきだったか
区間に含まれる名産物は重複する可能性があるので、重複しないように数える工夫が重要。今回の問題の場合、区間の長さで分類することで、「必ず1つ以上含まれる or 含まれるかどうかわからないが高々1つ」の区間に分類できる。「含まれるかどうかわからないが高々1つ」である区間は、長さ d ごとに数えると重複せずに数えることができる。
