AtCoder ABC 149 D - Prediction and Restriction (2Q, 茶色, 400 点)

ちょっと問題を理解するのが大変かもしれない

問題へのリンク

問題概要

ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。

• グーを出して勝つと 点
• チョキを出して勝つと 点
• パーを出して勝つと 点

が得られる。ただし 回目以降は、 回前に出したものと同じ手を出すことはできない。得られる得点の最大値を求めよ。

制約

• 

考えたこと

まず大事な視点として、たとえば のとき

• 1 回目、5 回目、9 回目、...
• 2 回目、6 回目、10 回目、...
• 3 回目、7 回目、11 回目、...
• 14回目、8 回目、12 回目、...

という各系列は完全に独立に考えて OK！！！よって、基本的には「連続して同じ手を出せない」という問題と同一視できるのだ。

実は Greedy

ここまでの考察で、「連続して同じ手は出せない」という制約下でなるべく得点を稼ぐ問題に帰着されたので、それを考える。場合分けして状況を考えると...

• ロボットが連続して異なる手を出すとき： どちらにも勝てる
• ロボットが連続して同じ手を出すとき：どちらかだけ勝てる

という風になっていることがわかる。より具体的には、たとえばロボットが

rrrrrgggbrrggbbbb

という風に出すとき、

rrrrr ggg b rr gg bbbb
oxoxo oxo o ox ox oxox

という感じにできる。ロボットの手として「同じものが連続している区間」ごとに考えて良くて、それぞれ約半分勝つことができるイメージだ。

実装上は、

• ロボットの手が前回と異なるなら：問答無用で勝てる
• ロボットの手が前回と同じで、前回は負けたとき：今回は勝てる
• ロボットの手が前回と同じで、前回は勝ったとき：今回は負ける

という風にすれば OK。

#include <bits/stdc++.h>
using namespace std;

// r -> P, s -> R, p -> S
int main() {
    int N, K, R, S, P;
    string T;
    cin >> N >> K >> R >> S >> P >> T;
    auto score = [&](int i) {
        if (T[i] == 'r') return P;
        else if (T[i] == 's') return R;
        else return S;
    };
    long long res = 0;
    for (int k = 0; k < K; ++k) {
        bool last = false;
        for (int i = k; i < N; i += K) {
            if (i >= K && T[i-K] == T[i] && last) last = false;
            else res += score(i), last = true;
        }
    }
    cout << res << endl;
}