Gathering Children [AtCoder Beginner Contest 136 D]

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

前提知識

• ダブリング

解説

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

まずは、実験する。
最終的な状態では、周期2でループすることが分かる。
これは、RLの所で行き来するので、周期2になる。

ほぼ無限回数移動させるが、このループの状態になるまでには10⁵回くらい移動すれば十分。
よって、各マスについて10⁵回移動させたときの場所が分かれば答えられる。
このままだとO(N²)

この移動を高速に行うにはダブリングを使おう。
dp[p][i] := i番目のマスから2^p回移動した先のマス
これを埋めていく。
これはdp[p+1][i] = dp[p][dp[p][i]]のように更新できるので、O(NlogN)で構築可能。
あとは、dp[32][i]を使って各マスにいる子供の人数を求めよう。

string S;
int N;
int dp[33][101010];
int ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    rep(i, 0, N) {
        if (S[i] == 'R') dp[0][i] = i + 1;
        else dp[0][i] = i - 1;
    }

    rep(p, 0, 32) rep(i, 0, N) dp[p + 1][i] = dp[p][dp[p][i]];

    rep(i, 0, N) ans[dp[32][i]]++;
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}