[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)\]
となります。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません