ABC149 D - Prediction and Restriction

問題原文

atcoder.jp

問題要旨

グーで勝ったら 点、チョキで勝ったら 点、 パーで勝ったら 点、という条件で、機械とじゃんけんをする。
あいこ、負けは０点とする。相手のこれから出す手が全て長さ の文字列 としてわかっている時、最適に手を出すことで最高何点得られるか？
ただし、 回前に出した手と同じ手を出すことはできない。

• 

解法

modK で を 個のグループに分割できる。
分割後のグループで解くべき問題は、「最大何点取れるか？ただし直前と同じ手は出せない。」になる。これはDPとかで解ける。

実は貪欲でも解ける。modK でのグループ分割も実は必要ない。
簡単のために とした上で、 とする。
p を２回連続で出せないため、 p 以外で、 そして３戦目に s を出せるような手（３戦目の勝ちを邪魔しない手）を出したい。
そしてこれを満たすような手が、毎回最低１つ存在することは楽に示せる。

「１戦目と２戦目のうちどっちで勝つべきか？」という疑問が浮かぶかもしれないが、上記の考え方を元にして などを想像すれば、「勝てる時に勝っておいて損しないこと」もわかる。これで貪欲の正当性が示せた（はず）。

まとめると、 - 勝てる時には勝っておく - そうでない時には、 回後に邪魔にならない手を出す。

以上のようにすることで最適な解が得られる。

実装

実装においては、 回後に邪魔にならないような手を求める必要はない。
最低１つ存在することはわかっているので、 「何も手を出さず、得点は０」ということにして処理をすればいい。

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())


ans = 0
commands = [''] * N
for i, t in enumerate(T):
    if t == 'r':
        command = 'p'
        point = P

    elif t == 's':
        command = 'r'
        point = R

    elif t == 'p':
        command = 's'
        point = S

    if (i - K >= 0) and (commands[i -  K] == command):
        command = ''
        point = 0

    ans += point
    commands[i] = command

print(ans)

感想

今回は使わなかったけど、 「modK で問題の簡単化・グループ化」という発想はすぐに取り出せるようにしておきたい。
ある操作をしても損することは絶対ないかも？ という発想も！