2011年12月23日
情報オリンピック日本委員会
解説
単純な解法として，パスタの候補を全て列挙して，
その中で条件をみたすものを数えるという方法がある．
まだ予定の決まっていない N-K 日のそれぞれに対し，
3 種類のパスタから 1 つを選ぶ．
選び方は全部で 3N-K 通りあるので，これを全て調べればよい．
この方法でも部分点を取ることはできる．
しかし，この方法はとても効率が悪いため，N-K の値が大きい入力データでは競技時間内に正解を求めることはできない．
そこで次のように考えよう．
1 日目～ i + 1 日目のパスタがすでに決まっていたとしよう．
i + 2 日目以降のパスタを決める際には，i 日目と i + 1 日目のパスタの情報だけが用いられる．
「i 日目のパスタが A で，i + 1 日目のパスタが B だったときの i + 2 日目以降の予定の個数」を f(i,A,B) とおけば，f(i,A,B) は f(i + 1,A',B') の組み合わせで書けることが分かる．
全ての A', B' の組（全部で 3 × 3 = 9 通りある）に対して f(i + 1,A',B') が計算できれば，f(i,A,B) が計算できる．
f(i,A,B) に関する漸化式を立てて，f(i,A,B) を i が大きい方から順番に計算していけば，予定の個数を効率良く計算できる．
このような方法を動的計画法という．
または，漸化式を立てた後で，計算結果をメモしながら再帰を行う「メモ化再帰」という方法を用いてもよい．
なお，この問題では予定の数は非常に大きな数になるので，
計算結果のオーバーフローには注意が必要である．
10000 で割った余りを計算しながら予定の個数を数えていく必要がある．
