けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

問題概要

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

  • グーを出して勝つと  R
  • チョキを出して勝つと  S
  • パーを出して勝つと  T

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

制約

  •  2 \le N \le 10^{5}

考えたこと

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

  • 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;
}