AtCoder: ABC149-D Prediction and Restriction (400)

問題はこちら

atcoder.jp

回じゃんけんを行う。買った場合、以下のように点が与えられる。

• グーで勝った時、 点
• チョキで勝った時、 点
• パーで勝った時、 点

ただし、ちょうど 回前に出した手と同じ手は出せない。

相手の出す手が事前に全て文字列 で与えられている時、最適に選ぶと最大何点得る事ができるか求めよ。

考え方

DPすればいいなという見方にはなる。普通にやると 回前に出した手を覚えておければいいのだが、DP遷移がうまく実装できない。

そこで、今回は一回ずつの試行は 回前の試行にのみ依存し、そのほかの回数とは独立であることに注目する。これを手がかりとすると、「 回前と同じ手は出せない」 → 「 で見たとき、前回と同じ手は出せない」となることに気づく。

こうなればあとは普通のDPと一緒で、 の世界でそれぞれに対して前回と同じ手を今回は選ばないように遷移して数え上げ、最後にその和を取れば答えになる。

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, k;
    cin >> n >> k;
    ll r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    const ll RR = 0, SS = 1, PP = 2;

    ll ans = 0;
    for (ll i = 0; i < k; ++i) {
        vector<vector<ll>> dp(n / k + 10, vector<ll>(3));
        ll tmp = 0;
        for (ll j = i; j < n; j += k) {
            ll idx = j / k;
            rep(now, 3) {
                rep(prev, 3) {
                    if (idx > 0 && now == prev) continue;
                    dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev]);

                    if (t[j] == 'r' && now == PP) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + p);
                    }
                    if (t[j] == 's' && now == RR) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + r);
                    }
                    if (t[j] == 'p' && now == SS) {
                        dp[idx + 1][now] = max(dp[idx + 1][now], dp[idx][prev] + s);
                    }
                }
                tmp = max(tmp, dp[idx + 1][now]);
            }
        }
        ans += tmp;
    }
    cout << ans << '\n';
    return 0;
}

Submission #14117271 - AtCoder Beginner Contest 149

別解

greedy解もあるらしい。 回先で同じ手で勝てるなら、早いうちに手を出して勝ったほうが得になるので、

• 今勝てるなら勝てる手を出す。
• 勝てる手を出せない場合は、次の 回先の手で勝ちたい。なので、 回先の手を邪魔しない手を出す。