ベスパリブ

ベスパもってないです。バイク買いました。

ABC 136: D問題の解説 (Python3)

問題: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()

計算量は O(N) です。