D - Prediction and Restriction

・問題URL

https://atcoder.jp/contests/abc149/tasks/abc149_d

・発想

・負けとあいこが得点同じ
・制限はあるものの、ある程度出す手に自由度があり、しかも求めるのは最大値→貪欲法か？
・得点が多いときは絶対勝ちたい！→無理
・K回前に出した手が今出せる手に影響する→DP？
・DPまだガチの初歩的なやつ（カエルぴょんぴょん）しかマスターしてないからやっぱ貪欲でいけないかなあ
・仮に出す手の制限がないとして、全部勝った時の得点が理論値。実際は制限があるので、K＋１回目から見ていくと絶対に勝てないX回目が存在。X＋K回目はできれば勝ちたい。ここで発想の１つ目をみると、ここで残り２種のうちうまく手を選べば被害は理論値-（X回目で勝った時のポイント）で済む。いけそう

・解法

K回目までは全部勝つ。K＋１回目以降は勝てるなら勝つ。勝ち手が出せないなら、勝ち手とも、そのK回後に出せば勝てる手とも違う残りの手を出しておけば被害がその回で得られるはずだったポイントで最小になる。
ちなみに、K回目までは後先考えず勝ち続けるのが最適かどうかよくわからないまま実装したが、同じ手で後で勝つのも先に勝つのもまあ同じじゃね？ってのと、勝てるうちに勝っておかないと最後に損する場合がある具体例（例えば、N=５,K=1,筐体の出す手が全部グーのとき、PGPGPのようにだしたほうが、GPGPGより高得点）を考えると納得できた。
実装面では、Tにrspのどれとも異なる文字ｘをめっちゃ長くつなげるとK回後が存在しないときの処理が楽。

・コード

長い（）

int main(){
  
  ll N,K,R,S,P;
  cin>>N>>K>>R>>S>>P;;
  string T;
  cin>>T;
  vector<char>t(N);
  rep(i,N+10)T+='x';//工夫した
  
  ll ans=0;
  rep(i,MIN(N,K)){
    if(T[i]=='r'){
      ans+=P;
      t[i]='p';
    }
    else if(T[i]=='s'){
      ans+=R;
      t[i]='r';
    }
    else {
      ans+=S;
      t[i]='s';
    }
  }

  for(int i=MIN(N,K);i<N;i++){
    if(T[i]=='s'){
      if(t[i-K]=='r'){
        if(T[i+K]=='r')t[i]='s';
        else if(T[i+K]=='s')t[i]='s';
        else t[i]='p';
      }
      else {
        ans+=R;
        t[i]='r';
    }
  }
    if(T[i]=='p'){
        if(t[i-K]=='s'){
          if(T[i+K]=='s')t[i]='p';
          else if(T[i+K]=='p')t[i]='p';
          else t[i]='r';
        }
        else {
          ans+=S;
          t[i]='s';
      }
    }
    if(T[i]=='r'){
        if(t[i-K]=='p'){
          if(T[i+K]=='p')t[i]='r';
          else if(T[i+K]=='r')t[i]='r';
          else t[i]='s';
        }
        else {
          ans+=P;
          t[i]='p';
      }
    }
  }
 
  cout<<ans<<endl;

}