2017ACM-ICPC アジア地区大会 問題A

　意外にもあっさり解けたので解法を残しておきます。たぶんオーソドックスな動的計画法でしょう。

　漸化式を次のように定めます。

　dp[i] := 黒、白、黒、…黒の順番でチョコレートが積まれていて、なおかつ高さがちょうど i になるようなチョコレートの積み方の総数

　ここで、何らかの形で黒、白、黒、…黒の順番でチョコレートを積み上げることができているとします。この時、さらにその上にチョコレートを積み上げる方法としては、

(1')厚さ１の白いチョコレートを載せ、さらにその上に厚さ１の黒いチョコレートを載せる

(2')厚さ１の白いチョコレートを載せ、さらにその上に厚さ k の黒いチョコレートを載せる

の2通りしかありません。

　このことから、高さがちょうど i になるようにチョコレートを積み上げるためには、

(1)高さ i - 2 の状態から(1')のようにチョコレートを積む

(2)高さ i - (k + 1) の状態から(2')のようにチョコレートを積む

(3)高さ i の黒のチョコレートを1つだけ地べたに置く ( i = 1, k の場合のみ)

のいずれかになることが分かります。

　ゆえに、i = 1 or i = k のとき dp[i] = 1、それ以外のとき dp[i] = 0 となるように dp[i] を初期化し、漸化式 dp[i] += dp[i - 2] + dp[i - (k + 1)] を満たすようにループを回せば、計算量O(l)でこの問題を解くことが可能です。