D - Gathering Children

Quiz

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

AC Code

https://atcoder.jp/contests/abc136/submissions/6718753

解法

• ダブリングやDPを使わない方法です
• 大量に移動した後は、どこかのRLに落ちて振動します
• 全てのRLの位置を調べておく
• 各子供について、Rなら右側のRLに落ち、Lなら左側のRLに落ちる
• lower_boundすれば、行き先のindexが求まるので、移動量の偶奇を見て、RLのどちらかが決まる

Code

    string s; cin >> s;
    ll L = s.size();
 
    set<ll> se;
    // RLなるi
    FOR(i, 0, L-1){
        if(s[i]=='R' && s[i+1]=='L'){
            se.insert(i);
        }
    }
 
    vector<ll> C(L, 0); // 位置ごとに子供をカウント
    FOR(i, 0, L){
        if(s[i]=='R'){
            auto it = se.lower_bound(i);
            ll index = *it; // 最終的に落ちるRLの位置
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
        else{
            auto it = se.lower_bound(i);
            it--; // 自分より左側のRL
            ll index = *it;
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
    }
    vprint(C);