ブログを始めました~階段(Stairs)を解いた話~
自己紹介
tRueです。数学とプログラミングを趣味でやっているものです。
TwitterIDは@tRue_mathです。
暇なので階段の解説します
問題
https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf
情報オリンピック春合宿の問題です。JOI難易度6です。
一般的な階段上るDPの、段差の大きさがバラバラVerみたいな感じ。
登り方の通り数をmod1234567で求める。1234567、初めて見た。
考察
ある段差からどこの段差までいけるかは、
累積和と二分探索を駆使してO(logN)で求められそう。
各段差からたどり着ける場所に配るDPで解けそうだけど、
たどり着ける場所を一つずつ見ると、O(N²logN)になってしまうので良くない。
今いる段差から、たどり着ける範囲全体に配ればいいので、
imos法的に区間に足し算するイメージでやればO(NlogN)に落とせそう。
実装
累積和、二分探索の部分は普通にできるので良いとして、
imos法的に区間に足し算をする実装を考える。
サンプルケースを例にしてみると、
下の図みたいなもの(伝われ)が実装できればいい
もし仮に、下の図みたく最後まで足し切るのであれば、
ただの累積和の実装で解ける。
ここで、下の図のように考えると、
足し算の累積和と引き算の累積和をうまく作れば解けそうだと分かる。
これを実装して、こんなコードになりました
変数名が壊滅的にわかりにくいですが、
dp[i]が図でいう黒矢印、
mi[i]が図でいう赤矢印になっています。
これで無事、
「累積和二分探索1次元ナップサックDPmod付き~季節のimosを添えて~」
で階段をACすることができました。わーい。