[AtCoder] 三井住友信託銀行プログラミングコンテスト2019 E – Colorful Hats 2

問題

方針

\( A_1 \neq 0 \) のとき場合の数は \( 0 \) となります。ここで、\( d_i(j) \) を \( i \) 番目までの人を調べ終えた時、同じ帽子が \( j \) 個であるパターン数とします。初期値は、\( d_0(0) = 3 \) です。また、\( i \) 番目までの人を調べ終えた時の場合の数を \( p_i \) とします。初期値は \( p_0 = 1 \) です。\( A_1 = 0 \) であるとき、\( p_1 = p_0d_0(A_1) \) となり、\( d_1 \leftarrow d_0 \) として、

\begin{eqnarray}
d_1(A_1) & \leftarrow & d_1(A_1) – 1\\
d_1(A_1 + 1) & \leftarrow & d_1(A_1 + 1) + 1
\end{eqnarray}

と更新されます。\( d_i \) と \( d_{i + 1} \) で変わる値は \( 2 \) 箇所なので、\( d_i(j) \) を \( d(i) \) と再定義して使いまわすことにします。したがって、

\begin{eqnarray}
p_i &=& p_{i – 1}d(A_i) \\
d(A_i) & \leftarrow & d(A_i) – 1\\
d(A_i + 1) & \leftarrow & d(A_i + 1) + 1
\end{eqnarray}

となります。\( i \) 番目の人がある帽子を被ると、同じ帽子が \( A_i \) 個であるパターンが \( 1 \) 減り、 同じ帽子が \( A_i + 1\) 個であるパターンが \( 1 \) つ増えます。

コード

 

参考

感想

こういう問題苦手です。解説読んでもあまり理解できませんでした。