[AOJ] No. 0568 パスタ (Pasta)

問題

方針

\( 3 \) 日以上同じパスタを選んではいけないという制約がポイントです。\( i + 1 \) 日目の予定を決めるためには、\( i \) 日目と \( i – 1 \) 日目の予定が影響することを考えて動的計画法を行います。ここで、\( d(i, j, k) \) を \( i \) 日目にパスタ \( j \) を選び、\( i + 1 \) 日目にパスタ \( k \) を選ぶ時の場合の数とします。また、\( d \) は \( 0 \) で初期化します。

ここで、\( i \) 日目のパスタの予定を \( c_i \) とします。予定がないときは \( c_i = -1 \) とします。

初期値

\( c_1 = -1 \wedge c_2 = -1\) のとき

このとき、\( d(1, i, j) = 1  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3)\) となります。これは、\( 1 \) 日目と \( 2 \) 日目に予定が入っていないことになります。

\( c_1 \neq -1 \wedge c_2 \neq -1\) のとき

このとき、\( d(1, c_1, c_2) = 1 \) となります。

\( c_1 = -1 \wedge c_2 \neq -1\) のとき

このとき、\( d(1, i, c_2) = 1 (1 \leq i \leq 3)\) となります。

\( c_1 \neq -1 \wedge c_2 = -1\) のとき

このとき、\( d(1, c_1, i) = 1 (1 \leq i \leq 3)\) となります。

更新式

\( c_i = -1 \wedge c_{i+1} = -1\) のとき

このとき、\( d(i, j, k) \gets d(i, j, k) + d(i – 1, l, j) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge 1 \leq l \leq 3 \wedge j \neq k \wedge k \neq l)\) となります。右辺の \( d(i, j, k)\) と \( d(i – 1, l, j) \) において、\( j \) が共通しているのは、\( i \) 日目の \( j \) を選択するという遷移は、\( i -1 \) 日目において、次の日に \( j \) を選択していなければならないからです。

\( c_i \neq -1 \wedge c_{i+1} \neq -1\) のとき

このとき、\( d(i, c_i, c_{i+1}) \gets d(i, c_i, c_{i+1}) + d(i – 1, j, c_i) \  (1 \leq j \leq 3 \wedge c_i \neq c_{i+1} \wedge j \neq c_i)\) となります。

\( c_i = -1 \wedge c_{i+1} \neq -1\) のとき

このとき、\( d(i, j, c_{i+1}) \gets d(i, j, c_{i+1}) + d(i – 1, k, j) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge j \neq c_{i+1} \wedge j \neq k)\) となります。

\( c_i \neq -1 \wedge c_{i+1} = -1\) のとき

このとき、\( d(i, c_i, j) \gets d(i, c_i, j) + d(i – 1, k, c_i) \  (1 \leq i \leq 3 \wedge 1 \leq j \leq 3 \wedge j \neq c_{i} \wedge j \neq k)\) となります。

コード