第11回日本情報オリンピック 予選 D - パスタ
お題箱より。
解法
※実装に合わせて、0-indexedでの記述とします。最初の日は 日目です。
日目から順番にパスタの種類を決めていくことにします。ルールは「事前に指定された日のパスタの種類は決まっている」ことと「3日連続で同じパスタを作ってはいけない」ことです。
日目のパスタの候補は、この日が事前に指定されていればその1種類、そうでなければ3種類になります。そしてパスタを選ぼうとした時にそれが「3日連続で同じ種類」にならないかどうかは、1日前と2日前のパスタの種類だけを覚えておけば判定できます。
ここから「状態をまとめる」という考え方をして、DPを組むことができます。すなわち 日目のパスタまでの選び方を1つ1つ区別すると膨大な数になるかもしれませんが、そのうち 日目と 日目のパスタが同じものはまとめてしまうことができます。
そのため、DPの状態を以下のように定義します。
- 日目までのパスタの選び方で、 日目のパスタが 、 日目までのパスタが であるようなものの総数
ここで はパスタの種類を示す整数で、実装上には を使うことにします。
遷移を考えます。 日目に選ぼうとするパスタを とします。これは先ほど書いた通り、この日が事前に指定されていればその1通り、そうでなければ3通りの遷移を全て試します。そして のときは遷移をストップし、そうでなければ に遷移します。
これを最後まで計算し、 を全ての について合計したものが答えとなります。
ただ、この問題で地味に面倒なのが初期条件です。最初の日には「前の2日に食べたパスタ」が存在しないので初期条件の扱いに困ります。適当にどれかのパスタを食べたことにしてしまうと、実際には違うのに「3日連続」の条件に引っかかってしまう危険性があります。
色々対処法はありますが、今回の場合は「3日連続」の条件を「(0-indexedなので)今が2日目以降、かつ 」という風に書くのが一番シンプルだと思います。こうすれば初期条件における「前の2日に食べたパスタ」は判定に関係しないので、適当に設定してしまっても大丈夫です。