[AtCoder] ABC 149 D – Prediction and Restriction

2020年12月17日

問題

方針

動的計画法を行います。\( 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)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, K, R, S, P;
    cin >> N >> K >> R >> S >> P;
    string T;
    cin >> T;
    // 0: R, 1: S, 2: P
    int t[N];
    int v[3] = {R, S, P};
    for (int i = 0; i < N; i++) {
        if (T[i] == 'r') t[i] = 2;
        if (T[i] == 's') t[i] = 0;
        if (T[i] == 'p') t[i] = 1;
    }
    int d[N][3]{};
    for (int i = 0; i < K; i++) {
        d[i][t[i]] = v[t[i]];
        for (int j = i + K; j < N; j += K) {
            for (int k = 0; k < 3; k++) {
                if (t[j] == k) {
                    d[j][k] = max(d[j - K][(k + 1) % 3], d[j - K][(k + 2) % 3]) + v[k];
                } else {
                    d[j][k] = max(d[j - K][(k + 1) % 3], d[j - K][(k + 2) % 3]);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= K; i++) {
        ans += max(d[N - i][0], max(d[N - i][1], d[N - i][2]));
    }
    cout << ans << "\n";
    return 0;
}