ABC136 D Gathering Children

AtCoder

問題

atcoder.jp

解説

  • 最終的にどのような状態になるのか

軽くシミュレートをすると、子供たちは、最終的に"RL"または"LR"であるような境界を行き来するだけになります。文字列の長さに対して10^ {100}回も移動するので、これは確実です。

そこで、このような境界において子供達が右側と左側のどちらに溜まるのかをうまく決定したいという気持ちになります。

  • 偶奇性

"RL"という地点があり、今"R"に居る状態からこの境界を行き来することを考えます。
1回目の移動：L
2回目の移動：R
3回目の移動：L
4回目の移動：R
というように、これはもちろん交互になるため、移動回数の偶奇を見れば分かりそうです。そして、問題文にある 10^ {100}というのは偶数回であると気づくことも重要です。

  • 遠くからやってくる子供達

"RRRRL"という文字列があるとします。
10^ {100}回移動するとき、それぞれの子供達はどちらに溜まるでしょうか。
あらかじめ子供達に仮の番号をつけた状態でシミュレーションすると、
[1] [2] [3] [4] [5]
1回目 [-] [1] [2] [3,5] [4]
2回目 [-] [-] [1] [2,4] [3,5]
3回目 [-] [-] [-] [1,3,5] [2,4]
4回目 [-] [-] [-] [2,4] [1,3,5]
(4(偶数)回目から10^ {100}回目までも偶数回の移動なので、変わらず)
10^ {100}回目 [-] [-] [-] [2,4] [1,3,5]

というように、偶数番目の子供達と奇数番目の子供達に分かれるということが言えそうです。
というわけで、"R"や"L"が連続して並んでいる区間に対して、これらの処理をしていけば、問題が解けそうです。

以下のコードでは、最初"R"だけについて処理をした後に、文字列を反転させて"L"だけについて処理をしています。こうすることで、常に右に進むものとして扱えるので分かりやすいです。

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
template<typename T> 
void print(vector<T> v){
    for(int i=0;i<v.size();i++){
        if(i)cout<<" ";
        cout<<v[i];
    }
    cout<<endl;
}

signed main (){
    string s;
    cin>>s;
    vector<int> ans(s.size(),0);
    //最初はRだけについて処理
    rep(i,0,s.size()){
        if(s[i]=='R'){
            int idx=1;
            int ct[2]={};
            ct[idx%2]++;
            while(i+1<s.size() and s[i]==s[i+1]){
                idx++;
                ct[idx%2]++;
                i++;
            }
            if(idx%2==1){  //区間の長さが奇数なら
                ans[i+1]+=ct[0]; //偶数番目の要素が境界の右に溜まる
                ans[i]+=ct[1];  //奇数番目の要素が境界の左に溜まる
            }else {
                ans[i+1]+=ct[1];
                ans[i]+=ct[0];
            }
        }
    }

    reverse(all(s));
    reverse(all(ans));
    //今度はLだけについて処理
    rep(i,0,s.size()){
        if(s[i]=='L'){
            int idx=1;
            int ct[2]={};
            ct[idx%2]++;
            while(i+1<s.size() and s[i]==s[i+1]){
                idx++;
                ct[idx%2]++;
                i++;
            }
            if(idx%2==1){
                ans[i+1]+=ct[0];
                ans[i]+=ct[1];
            }else {
                ans[i+1]+=ct[1];
                ans[i]+=ct[0];
            }
        }
    }
    reverse(all(ans));
    print(ans);
}

ct[2] が、連続する区間に対して偶数番目と奇数番目である要素を数えるための配列です。ct[0]、ct[1]が境界のどちらに溜まるのかは、その区間の長さによるので、そこだけ場合分けをしてあげます。

数を数えるところは関数化するのが綺麗なんでしょうが、競プロの範囲ではそこまで考えなくても良いと思っているのでそのままです。。