ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

第11回日本情報オリンピック 予選 D - パスタ

お題箱より。

D - パスタ (Pasta)

解法

※実装に合わせて、0-indexedでの記述とします。最初の日は  0 日目です。

 0 日目から順番にパスタの種類を決めていくことにします。ルールは「事前に指定された日のパスタの種類は決まっている」ことと「3日連続で同じパスタを作ってはいけない」ことです。

 i 日目のパスタの候補は、この日が事前に指定されていればその1種類、そうでなければ3種類になります。そしてパスタを選ぼうとした時にそれが「3日連続で同じ種類」にならないかどうかは、1日前と2日前のパスタの種類だけを覚えておけば判定できます。

ここから「状態をまとめる」という考え方をして、DPを組むことができます。すなわち  i-1 日目のパスタまでの選び方を1つ1つ区別すると膨大な数になるかもしれませんが、そのうち  i-1 日目と  i-2 日目のパスタが同じものはまとめてしまうことができます。

そのため、DPの状態を以下のように定義します。

  •  dp\lbrack i \rbrack\lbrack a \rbrack\lbrack b \rbrack =  i-1 日目までのパスタの選び方で、 i-2 日目のパスタが  a i-1 日目までのパスタが  b であるようなものの総数

ここで  a, b はパスタの種類を示す整数で、実装上には  0, 1, 2 を使うことにします。

遷移を考えます。 i 日目に選ぼうとするパスタを  c とします。これは先ほど書いた通り、この日が事前に指定されていればその1通り、そうでなければ3通りの遷移を全て試します。そして  a=b=c のときは遷移をストップし、そうでなければ  dp\lbrack i+1 \rbrack\lbrack b \rbrack\lbrack c \rbrack に遷移します。

これを最後まで計算し、 dp\lbrack N \rbrack\lbrack a \rbrack\lbrack b \rbrack を全ての  a, b について合計したものが答えとなります。

ただ、この問題で地味に面倒なのが初期条件です。最初の日には「前の2日に食べたパスタ」が存在しないので初期条件の扱いに困ります。適当にどれかのパスタを食べたことにしてしまうと、実際には違うのに「3日連続」の条件に引っかかってしまう危険性があります。

色々対処法はありますが、今回の場合は「3日連続」の条件を「(0-indexedなので)今が2日目以降、かつ  a=b=c」という風に書くのが一番シンプルだと思います。こうすれば初期条件における「前の2日に食べたパスタ」は判定に関係しないので、適当に設定してしまっても大丈夫です。

ACコード

Submission #11350713 - 第11回日本情報オリンピック 予選(オンライン)