JOI2010春合宿 C stairs - 階段 (Stairs) - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

${1\le N\le 10^5}$ の段数がある階段がある. その階段の ${i}$ 番目の段差の高さは ${1\le h_i}$ であり, ${h_1+h_2 \ldots h_N\le 5×10^8}$ である. 段差の和が ${P}$ 以下の段を一度に上ることができるとき, 階段の上り方の数を1234567で割った余りを求めよ．

思考の流れ

ぱっと見DPというのはすぐわかる. ${dp[i]：i}$ 段目につく上り方の総数, とすると更新式は

$dp[i]=\sum_{j} {dp[j]}$ ( ${j}$ は ${i}$ 段目の段差との高さの差が ${P}$ 以下であるもの)

${\downarrow}$

${i}$ 段目の段差との高さの差が ${P}$ 以下であるもの和をいちいち求めていたら1回の更新に ${O(N)}$ かかる.
連続する区間の和の形になっているので累積和を使えそう.
後は ${i}$ 段目の段差との高さの差が ${P}$ である中で最小のものの位置さえわかればいいようになった.

${\downarrow}$

地上( ${0}$ 段目)の高さ ${0}$ とし, 地上からの各段差までの高さ ${H[i]}$ を持っておくと, ${j}$ 段目の段差と ${i}$ 段目の段差との高さの差が ${P}$ であるということは ${H[j]\le H[i]-P}$ ということになる. このような ${j}$ で最小なものは二分探索を行うことで求めることができる. 他にも尺取り法を用いても求めることができる.

提出プログラム

https://atcoder.jp/contests/joisc2010/submissions/11975093

感想

すぐに解法が浮かんだのでよかった. こういう問題好き.