JOI2010 春合宿 - Stairs

• 問題
• AC

$x$段目の地面からの高さを$H_x$とし、$x$段目までの上り方の総数を$f(x)$とする。$H_l \ge H_x - P$となるような最小の段を$l$段目とするとき、$f$の漸化式は

$$f(x) = \sum_{t \in [l, x)}f(t)$$

と書ける。このままDPすると間に合わないので累積和$S(x) := \sum_{t=0}^xf(t)$を考える。

$$f(x) = S(x-1) - S(l-1)$$ $$S(x) = f(x) + S(x-1)$$

が成り立つから、$S$の漸化式は

$$S(x) = 2S(x-1) - S(l-1)$$

とまとまる。$S$に関してDPすればよい。答えは$f(N) = S(N)-S(N-1)$である。

毎回$l$を二分探索で求めると計算量は${O}(N\log N)$。尺取り法で${O}(N)$。