概要

DPを用いて、時間計算量$O(N)$で求めることができます。

DPテーブルの定義

以降では以下のDPテーブルについて考えます。

$dp[i][j][k] := i日目までの献立を決めて、i+1日目以降カレーパンをj日、小豆パンをk日選択できない場合の数$

例えば、初日に小豆カレーパンを選んだ場合の数は、$dp[1][1][2]$(1日目まで献立を決め、カレーパンと小豆パンがそれぞれ1日、2日選べないため)となります。

初日の献立に制約はないので、DPテーブルの初期値は以下の通りになります。

$$dp[0][j][k] = \begin{cases} 1 & (if\; j = 0 \land k = 0) \\ 0 & (else\; if\; 0 \le j \le 1 \land 0 \le k \le 2) \end{cases}$$

DPテーブルの遷移

このDPを送るDPと思って、$dp[i][j][k]$から遷移する方法を考えます。

まず、4種類のパンについて$i+1$日目に選択できるかどうかを以下の条件で判定できます。

• ノーマルパンはいつでも選択できます。
• カレーパンは$j = 0$のときのみ選択できます。
• 小豆パンは$k = 0$のときのみ選択できます。
• 小豆カレーパンは$j = 0 \land k = 0$の時のみ選択できます。

つぎに、遷移先を$dp[i+1][j'][k']$と置くと、$j',k'$は以下のように求められます。

• ノーマルパンを選んだとき、$j' = \max(j-1,0), k' = \max(k-1,0)$
• カレーパンを選んだとき、$j' = 1, k' = \max(k-1,0)$
• 小豆パンを選んだとき、$j' = \max(j-1,0),k' = 2$
• 小豆カレーパンを選んだとき、$j' = 1, k' = 2$

求めたい答えは$N$日目のすべての場合の数の和になります。

$$ans = \sum_{j=0}^{1}{\sum_{k=0}^{2}{dp[N][j][k]}}$$