[AtCoder] ABC 149 D – Prediction and Restriction

問題

方針

動的計画法を行います。\( N \) 回のジャンケンにおいてジャンケンの手が制約されるグループは \( K \) 個存在します。例えば、\( K = 2 \) のとき、\( 0, 2 ,4, \cdots \) と \( 1, 3, 5, \cdots \) という二つのグループに分けることができます。 ここで、\( d(i, j) \) を \( i \) 回目のジャンケンにおいて \( j \ (0 \leq j \leq 2)\) を出したときのスコアの最大値とします。グループ \( g \ (0 \leq g \leq K – 1)\) に対して、この配列を更新します。ここで、\( v_j \) を \( j \) で勝った時の得点とします。初期値は、各グループの最初の手番において \( a \) を出して得点できる場合、\( d(g, a) = v_a \) とします。また、\( i \leftarrow i + K \) と更新していきます。

  • \( i \) 回目のジャンケンにおいて \( j \) を出して勝つ場合

\[d(i, j) = \max(d(i – g, (j + 1) \bmod 3), \ d(i – g, (j + 2) \bmod 3) ) + v_j\]

と更新できます。

  • \( i \) 回目のジャンケンにおいて \( j \) を出して勝てない場合

\[d(i, j) = \max(d(i – g, (j + 1) \bmod 3), \ d(i – g, (j + 2) \bmod 3) )\]

と更新できます。したがって、求める答えは、

\[ \sum_{i = 1}^{K} \max _{0 \leq j \leq 2}d(N – i, j)\]

となります。

コード