問題：AtCoder Beginner Contest 136: D - Gathering Children
公式解説PDF：https://img.atcoder.jp/abc136/editorial.pdf
公式解説動画：https://youtu.be/lyHk98daDJo?t=3172
解説
発想としてはランレングス法です。
S=RRRL という例を考えます。
- i=0の人は最終的にどこにいるのか？
## 初期状態 i: 0 1 2 3 ----------- S: R R R L .
## 3回の操作のあと i: 0 1 2 3 ----------- S: R R R L .
## 4回の操作のあと i: 0 1 2 3 ----------- S: R R R L .
という風に、あとは奇数回の操作後はi=3のLに、偶数回の操作後はi=2のRにいることになります。
- i=1の人は最終的にどこにいるのか？
## 初期状態 i: 0 1 2 3 ----------- S: R R R L .
## 2回の操作のあと i: 0 1 2 3 ----------- S: R R R L .
## 3回の操作のあと i: 0 1 2 3 ----------- S: R R R L .
という風に、あとは偶数回の操作の後はi=3のLに、奇数回の操作の後はi=2のRにいることになります。
以上の考察から、初期位置がRの場合で、初期位置から折返し地点までの距離を d とすると（ここで折り返し地点とは、操作中に到達するLのこと）、
- dが奇数のとき、
- 偶数回の操作の後は折返し地点の1つ左側に収束
- 奇数回の操作の後は折返し地点に収束
- dが偶数のとき、
- 偶数回の操作の後は折返し地点に収束
- 奇数回の操作の後は折返し地点の1つ左側に収束
ということがわかります。
同様に、初期位置がLの場合で、初期位置から折返し地点までの距離を d とすると（ここで折り返し地点とは、操作中に到達するRのこと）、
- dが奇数のとき、
- 偶数回の操作の後は折返し地点の1つ右側に収束
- 奇数回の操作の後は折返し地点に収束
- dが偶数のとき、
- 偶数回の操作の後は折返し地点に収束
- 奇数回の操作の後は折返し地点の1つ右側に収束
ということがわかります。
そして操作は10100回の偶数回行われるので、偶数回の操作後のことのみ考えれば良いことがわかります。
以上のような考察を紙にお絵かきしてシミュレーションすると、これはO(N)で実装できそうです。
ここまで気づいたら、あとはどうバグらせずシミュレーションを実装できるかという話なのですが、
文字列はRグループとLグループに交互に分けられそうだと思いつきます。
たとえば RRRLRLRLLLRRL という文字列を考えた場合、
R R R L R L R L L L R R L |_____||_||_||_||_||_____||___||_| 3 1 1 1 1 3 2 1
というふうに各グループの人数を数えることで、シミュレーションを簡単に実装できそうです。この部分がランレングス法の発想です。
まずはRグループについて考えます。
- グループの人数を cnt
- 折返し地点であるLまでの距離が偶数の人数を even_num
- 折返し地点であるLまでの距離が奇数の人数を odd_num
とそれぞれすると、
cnt = 3 even_num = cnt//2 odd_num = cnt - even_num
で求められるので、
- even_num 人は最終的に折返し地点に収束する
- odd_num 人は最終的に折返し地点の1つ左側に収束する
ことがわかります。
次にLグループについて考えます。
Rグループのときと同様の考察でcnt, even_num, odd_num を求めて、
- even_num 人は最終的に折返し地点に収束する
- odd_num 人は最終的に折返し地点の1つ右側に収束する
ことがわかります。
コーナーケース
- 特になし
実装
def solve(): S = input() N = len(S) ans = [0]*N # 最終的に出力する答え（10**100操作後に、各iに人がいる人数） # Rグループについて考える cnt = 0 # 現在のRグループの人数 for i, moji in enumerate(S): if moji == "R": cnt += 1 continue else: even_num = cnt//2 # 折返し地点までの距離が偶数の人の数 odd_num = cnt - even_num # 折返し地点までの距離が奇数の人の数 ans[i] += even_num # 折返し地点までの距離が偶数の人は、ans[i]に収束する ans[i-1] += odd_num # 折返し地点までの距離が奇数の人は、ans[i-1]に収束する cnt = 0 # Lグループについて考える cnt = 0 # Lグループの人数 for i in range(N-1, -1, -1): if S[i] == "L": cnt += 1 continue else: even_num = cnt//2 odd_num = cnt - even_num ans[i] += even_num ans[i+1] += odd_num cnt = 0 print(*ans) if __name__ == "__main__": solve()
計算量は です。
