「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。

問題へのリンク

問題概要

$N$ マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また初期状態では各マスに 1 人ずつ子どもがいる。今から以下の操作を $10^{100}$ 回実施する。

すべての子どもについて、現在自分のいるマスの文字が "L" の場合は左に移動し、"R" の場合は右に移動する

$10^{100}$ 回実施後の、各マスの人数を求めよ。

制約

$2 \le N \le 10^{5}$

考えたこと (解法 (1))

こういう問題は、一瞬「ん！？」となるので、手を動かしてみると見えてくる。たとえば

RRRRRRLLLLLRRRRRRLLLLLL

という感じだと、結果は

0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 0 6 6 0 0 0 0 0

となる。見てわかるのは「十分長い回数の移動を行うと、R と L の変わり目のところに皆集まる」ということだった。そして、上のような文字列は

RRRRRRLLLLL | RRRRRRLLLLLL

というふうに分割できる。つまり、"R...RL...L" という形をしたものだけを考えればよいことがわかる。

"R...RL...L" について

残る問題は、"R" が $A$ 個、"L" が $B$ 個あるときに、"RL" の変わり目にどのように集まるかを求めることだ。最終的に左の "R" 側に集まる子どもを "o" で表し、"L" 側に集まる子どもを "x" で表すことにすると、下のようになる。

R R R R R R | L L L L L L L
x o x o x o | x o x o x o x

整理すると、

"R" 側では "o" になるのは $(A+1)/2$ 個 (残りが "x")
"L" 側では "x" になるのは $(B+1)/2$ 個 (残りが "o")

となる。

コード

ランレングス圧縮に書き慣れていると実装しやすいかなと思う。計算量は $O(N)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = S.size();

    // ランレングス圧縮
    vector<int> res(N, 0);
    vector<int> div({0}); // 変わり目をメモ
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < N && S[j] == S[i]) ++j;
        div.push_back(j);

        // R と L の個数から、集計
        if (S[i] == 'L') {
            int A = div[div.size()-2] - div[div.size()-3];
            int B = div[div.size()-1] - div[div.size()-2];
            res[i-1] = (A+1)/2 + B/2;
            res[i] = A/2 + (B+1)/2;
        }

        // 更新
        i = j;
    }
    for (int i = 0; i < res.size(); ++i) cout << res[i] << " ";
    cout << endl;
}

解法 (2)：ダブリング

今回の問題に限らず、 $K$ 回操作後の結果を "思考停止で" 求められる方法として、ダブリングがある。まず次のデータは簡単に求められる。

next[0][v] ← マス $v$ から 1 ステップで行くマス ("L" なら $v-1$ 、"R" なら $v+1$ )

ここで添字の 0 は、ダブリングの 0 ステップ目であることを意味している。これを用いると、次のようなデータが求められる。

next[1][v] ← マス $v$ から $2^{1} = 2$ ステップで行くマス

具体的には next[1][v] = next[0][next[0][v]] と求められる。つまり「1 ステップで行くマスからさらに 1 ステップで行くマス」というわけだ。さらにこれを用いると

next[2][v] = next[1][next[1][v]] ← マス $v$ から $2^{2} = 4$ ステップで行くマス

が求められる。つまり「2 ステップで行くマスからさらに 2 ステップで行くマス」というわけだ。以下同様に、 $i = 0, 1, 2, \dots$ に対して

next[i+1][v] = next[i][next[i][v]]

とすることで、 $2^{0}, 2^{1}, 2^{2}, \dots$ ステップ先のマスが求められる。これを上手に組合せることで、 $K$ ステップ先のマスを求めることもできる！！！

$K = 10^{100}$ とするわけにはいかないけど、たとえば $k = 2N$ くらいで OK。十分大きい偶数なら OK。計算量は $O(N \log N)$ になる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;
int main() {
    string S;
    cin >> S;
    int N = S.size();

    vector<vector<int>> next(MAX, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'L') next[0][i] = i-1;
        else next[0][i] = i+1;
    }
    for (int d = 0; d+1 < MAX; ++d) {
        for (int i = 0; i < N; ++i) next[d+1][i] = next[d][next[d][i]];
    }

    vector<int> res(N, 0);
    int K = N*2;
    for (int v = 0; v < N; ++v) {
        int nv = v;
        for (int d = 0; d < MAX; ++d) {
            if (K & (1<<d)) nv = next[d][nv];
        }
        res[nv]++;
    }
    for (int v = 0; v < N; ++v) cout << res[v] << " ";
    cout << endl;
}