すぬさんの競プロノート (3) ABC149 D

問題：https://atcoder.jp/contests/abc149/tasks/abc149_d

じゃんけんマシーンが出す手の順番がわかっており、自分がK回前の手と同じものを出せないとき、じゃんけんマシーンで得られる最高得点を計算

解法アイデア：得点を諦める手番を愚直に決める。

例えば、最初の例　”rsrpr" (K=2) の場合、真ん中の”ｒ”だけが「諦め」の対象となる。これは、前から数えていったときに「K番目の先の手が同じ場合」に当たる。つまり、諦める手を”ｘ”とした際に、この例の場合"rsxpr"と置き換えられる。諦めた手のK番目先では、必ず勝てるように諦め方を調整可能なので、置き換え済みの文字列から得られる総得点を合計することで答えが求まる。

当然ながら、比較するときは前向きに探索したときに、K回目後に同じ手が出た場合、後の方の手を諦めるようにして、諦めた手のK回目後は必ず得点するようにすること（最初のif文）

 rep(i, N-K){
       if(T[i]==T[i+K] && T[i]!='x'){
           T[i+K] = 'x';
       }
   }
   ll ans = 0;
   rep(i,N){
       if(T[i]=='r')ans+=P;
       if(T[i]=='s')ans+=R;
       if(T[i]=='p')ans+=S;
   }
   cout<<ans<<endl;

なんと、DP解法もあるということ。ただ自分の考えるDPではなかった・・・