ABC365Dを解いた

筆者はレート700弱の茶色コーダ

今回はこの問題を解いていく

実装コード

貪欲法ではこのケースで解けないらしい。
なのでどの手を出すのかを使って動的計画法を組めば良いようだ。

from itertools import product
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

win = {"R":"P","P":"S","S":"R"}
lose = {"R":"S","P":"R","S":"P"}

def main():
    N = rI()
    S = rS()
    
    H =[{k:0 for k in "RPS"} for _ in range(N+1)]
    
    for i,s in enumerate(S,start=1):
        for k1,k2 in product("RPS",repeat=2):
            if k1 == lose[s] or k1 == k2: continue
            is_won = k1 == win[s]
            H[i][k1] = max(H[i][k1],H[i-1][k2] + (1 if is_won else 0))
                    
    ans = max(H[N].values())    
    print(ans)
    
if __name__ == '__main__':
    main()

まとめ

ABC365Dを解いた、実装には動的計画法を使用した。

感想

コンテストの時間中は貪欲法で実装してWAを出して、なぜ解けないのか分からず、
しかも、視点を変えて動的計画法をするという発想もなく、次の問題に飛ばしてしまった。

動的計画法を使いこなしたいと思っている身でこのようなミスは致命的といえる。
このようなミスが無いように動的計画法を使う意識を持っておきたい。