Edit

【pythonでABC149を解説】D - Prediction and Restriction

問題概要

問題ページ

D - Prediction and Restriction
D - Prediction and Restriction

問題ページへ移動する

問題文

高橋君は、ゲームセンターで「じゃんけんバトル」というゲームをプレイすることにしました。このゲームのルールは以下の通りです。

  • プレイヤーは筐体と \(N\) 回じゃんけんを行う (あいこの場合も \(1\) 回のジャンケンと数える)。
  • プレイヤーがじゃんけんで勝った場合、プレイヤーは出した手に応じて以下のスコアを得る (あいこや負けは \(0\) 点)。
    • グーで勝った場合、 \(R\) 点
    • チョキで勝った場合、 \(S\) 点
    • パーで勝った場合、 \(P\) 点
  • ただし、ちょうど \(K\) 回前のじゃんけんで出した手と同じ手を出すことはできない。( \(K\) 回目までのじゃんけんでは好きな手を出せる。)

筐体は、各回のジャンケンで出す手をゲーム開始前に決定します。能力者である高橋君は、ゲーム開始前にこれをすべて読み取りました。

高橋君が読み取った情報は文字列 \(T\) として与えられます。\(T\) の \(i(1 \leq i \leq N)\) 文字目が r のときは \(i\) 回目のじゃんけんで筐体がグーを出すことを、s のときはチョキを出すことを、p のときはパーを出すことを表します。

高橋君が \(N\) 回のじゃんけんで出す手を最適に選んだとき、ゲーム終了までに最大で合計何点を得られるでしょうか。

制約

  • \(2 \leq N \leq 10^5\)
  • \(1 \leq K \leq N-1\)
  • \(1 \leq R,S,P \leq 10^4\)
  • \(N,K,R,S,P\) は全て整数である。
  • \(|T| = N\)
  • \(T\) に含まれる文字は r , s , p のいずれかである。

問題の考察

ACコード

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    r, s, p = list(map(int, readline().split()))
    t = str(readline().rstrip().decode('utf-8'))
    ans = []
    score = 0
    for i, v in enumerate(t):
        if v == "r":
            ans.append("p")
        elif v == "s":
            ans.append("r")
        else:
            ans.append("s")
    for i, v in enumerate(ans):
        if i >= k:
            if ans[i-k] == ans[i]:
                ans[i] = "x"
    cnt = 0
    for v in ans:
        if v == "r":
            cnt += r
        elif v == "s":
            cnt += s
        elif v == "p":
            cnt += p
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit