TDPC F - 準急
駅1,...,iまでの停車駅の組み合わせをf(i)通りとする。K−1駅目までは止まるかどうか自由に選べるので
f(i)=2f(i−1)(2≤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)(K≤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とするとつじつまがあっていることがわかる。
