TDPC F - 準急

• 問題
• AC

駅$1, ..., i$までの停車駅の組み合わせを$f(i)$通りとする。$K-1$駅目までは止まるかどうか自由に選べるので

$f(i) = 2f(i-1) \qquad (2 \le i < K)$

である。$K$駅目以降は、すでに$K-1$駅連続で止まっている場合に停車できないため、このパターンを数えて$2f(i-1)$から引かなくてはいけない。端的に言うと、$f(i-1)$通りの組み合わせの中で$i$駅目に停車できないのは（停車を○、通過を✕で表すと）

駅	1	…	i-k-1	i-k	i-(k-1)	…	i-1	i
停車				✕	○	…	○

というパターンのみである。したがって、

$f(i) = 2f(i-1) - f(i-k-1) \qquad (K \le i < N)$

という漸化式が立つ。

最後に、$N$駅目には必ず止まるので特別扱いして

$f(N) = f(N-1) - f(N-k-1)$

となる。

さて、大枠はこれでよさそうなのだが、境界ケースについて考えてみる必要がある。まず、$K$駅目に停車できないのは1パターンのみなので、$K<N$なら$f(K) = 2f(K-1)-1$。また、$K+1$駅目には必ず止まれる¹ので$f(K+1) = 2f(K)$である。上の漸化式と比較すると、$f(0)=0, f(-1)=1$とするとつじつまがあっていることがわかる。

---

1. 1駅目に必ず止まるという条件による。 ↩︎