以下では R の数が L の数より多いケースのみを考えます（L の数が R の数より多い場合は左右反転させることで R の数が多いケースに帰着できます。また、 L, R の数が等しい場合は [1] [2] と同じ議論から \(t=0.5\) 以外では方向転換が起こらないことがわかります）。

\(S\) は長さ \(NK\) に拡張し、人々が向いている方向を変化させるのに応じて \(S\) も変化させることにします。

---

[1] \(t=0.5\) での変化

\(t=0.5,\ 1.5,\ 2.5,\ \dots\) で起こる変化について \(f_i=\) (\(S_0,\ S_1,\ \dots,\ S_i\) の中の R の数) \(-\) (\(S_0,\ S_1,\ \dots,\ S_i\) の中の L の数) を用いて考えます（便宜上 \(f_{-1}=0\) とします）。\(f_i\) を用いると人 \(i\) が向いている方向を変える条件は以下のように表現できます。

• \(S_i\)=L の場合、 \(0\leq f_i\) のとき向いている方向を変える
• \(S_i\)=R の場合、 \(f_{NK-1} < f_i\) のとき向いている方向を変える

とくに \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\) の場合、人 \(i\) は \(S_i\) によらず必ず向いている方向を変えます。

下図は \(N=15,\ K=1,\ S=\)RRRLRLLLLRRRLLR の場合の横軸 \(i\) に対する縦軸 \(f_i\) のグラフです。赤で書かれた線は \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\) かつ \(S_i=\)R の人で向きを変える人、青で書かれた線は \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\) かつ \(S_i=\)L で向きを変える人に対応しています。

このようにグラフの \(f_{NK-1} \) 以上の部分は \(t=0.5\) での変化ですべて下側に折れ返り、変化後は必ず \(\displaystyle f_{NK-1}=\max_{0 \le i \le NK-1}f_i\) が成り立つようになります（黄で書かれた線のように \(f_i < f_{NK-1}\) でも向いている方向を変えるような \(S_i\)=L の人はいますが、これらの変化は \(f_{NK-1}\) が最大値となることに正の寄与しかしません）。

---

[2] \(1 < t\) での変化

\(t=0.5\) で \(f_{NK-1}\) が \(f_i\) の最大値となるため、 \(t=1.5\) において \(S_i=\)R の人は向いている方向を変えません。このため、\(t=1.5\) での変化の後も \(f_{NK-1}\) は最大値のままです。以降の変化でも \(f_{NK-1}\) は最大値のままであり、\(S_i=\)R の人が向いている方向を変化させることはないことが帰納的にわかります。

このため、 \(1 < t\) での変化については 、\(S_i=\)L の人が最終的に \(S_i=\)R になるのかを考えればいいです。

---

[3] 最終的な \(S\) についての考察

\(S\) が \(1 < t\) で最終的にどのようになるのかについて考えます。

\(0 < f_i\) が成り立つ最小の \(i\) を \(k\) とします。まず \(i < k\) を満たす \(i\) に対する \(f_i\) は常に \(f_i \leq 0\) が成り立つので \(S_i\) は初期状態から変化しません。

つぎに \(k\leq i\) の人 \(i\) について考えます。まず \(S_k\) は常に R です。

ある時刻において人 \(k\) より右側に左を向いている人が \(n\ (1\leq n)\) 人いる場合、直後の変化では左を向いている人は \(n-1\) 人以下になります。

証明

そのような \(i\) の最小値を \(m\) とします。\(f_{m}=f_{m-1}-1\) について考えると、\(m\) の最小性から \(f_{m-1} \geq f_k=1\) なので \(0 \leq f_m\) です。

よって [1] で述べた条件を満たしていることからこの人は必ず向いている方向を右に変えます。

[2] で述べたように \(S_i=\)R の人が向いている方向を変化させることはないので、変化後、左を向いている人は \(n-1\) 人以下です。

よって人 \(k\) より右側で左をむいている人の数は、時刻 \(t=O(NK)\) で \(0\) 人になります（ちなみにもっとちゃんと評価すると \(t=O(\log N)\) で \(0\) 人になることがわかります）。

---

[4] まとめ

以上の考察から以下の結論が得られます。

• \(k \leq i\) かつ \(t=0\) において \(f_{NK-1} < f_{i}\) かつ \(S_i=\)Rである人 \(i\) は向いている方向を R \(\rightarrow\) L \(\rightarrow\) R と \(2\) 回だけ変化させる
• \(k \leq i\) かつ \(t=0\) において \(S_i=\)Lである人 \(i\) は向いている方向を L \(\rightarrow\) R と \(1\) 回だけ変化させる
• 上記の条件をいずれも満たさない人は向いている方向を \(1\) 度も変化させない

あとは \(k\) を求めて \(1,\ 2\) 番目の条件を満たす人の数を数えればいいです。これは \(f_{i}=\lfloor \frac{i}{N}\rfloor f_{N-1} + f_{i \bmod N}\) を利用すると、 \(O(N)\) で求めることができます。