D - Gathering Children

・問題URL

https://atcoder.jp/contests/abc136/tasks/abc136_d

・発想

・10¹⁰⁰回シミュレーションするのは無理。
・出力例を見ると、00120003400みたいに0の塊と1以上の塊がある。そうか、RLで挟まれるとそこを右往左往するだけか。しかも端っこは抜け出せないようになってるから絶対RRR・・・RRLL・・・LLLが何回か続く形の入力。
・RLの変わり目に人があつまって（10¹⁰⁰がバカでかいので絶対全員変わり目に行き着く）、その人数はRRR・・・RRLL・・・LLLのなかでなんか偶奇とか調べればよさそう（）。

・解法

実装途中でこんがらがったので、もうSの部分列RRR・・・RRLL・・・LLLだけの答えを出力するだけの関数を作った。これを何回か呼び出す。偶奇の場合分けは紙に書いたら整理できた。下のコードでは、入力したSの最後にRを付けて文字列を切断する工夫をした。

・コード

void howmany(string T){
 
 int N=T.size();
 int a=0;
 
 rep(i,N){
   if(T[i]=='R')a++;
 }
 if(a%2==1){
   rep(i,a-1)cout<<0<<" ";
   cout<<(N+2-1)/2<<" ";
   cout<<N-(N+2-1)/2<<" ";
   for(int i=a+1;i<N;i++)cout<<0<<" ";
 }
 else {
   rep(i,a-1)cout<<0<<" ";
   cout<<N-(N+2-1)/2<<" ";
   cout<<(N+2-1)/2<<" ";
   for(int i=a+1;i<N;i++)cout<<0<<" ";
 }

}

int main(){
  
 string S;
 cin>>S;
 S+='R';//工夫
 int N=S.size();
 vector<int>ans(N,0);
 bool Q=false;
 vector<string>A;
 string T="";
 
 rep(i,N){
   if(Q&&S[i]=='R'){
     A.push_back(T);
     T="";
     Q=false;
     i--;
   }
   else if(!Q&&S[i]=='R')T+='R';
   else if(S[i]=='L'){
     T+='L';
     Q=true;
   }
 }

 for(auto v:A)howmany(v);
  

}