第11回日本情報オリンピック 予選4

2011年12月23日
情報オリンピック日本委員会

問題
   パスタ (Pasta)

解説

単純な解法として,パスタの候補を全て列挙して, その中で条件をみたすものを数えるという方法がある. まだ予定の決まっていない 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 で割った余りを計算しながら予定の個数を数えていく必要がある.