ABC136 D - Gathering Children

問題原文

atcoder.jp

問題概要

L と R からなる、横一列に並んだ 個のマス目がある。１マス目は R で マス目 はL である。
各マスには最初子供が１人ずついる。各子供たちは、以下のルールにしたがって、 回移動する。

• 自分がいまいるマスが R なら右、 L なら左のマスに移動する。

全ての移動が完了したあと、各マスには何人の子供がいるか？

解法

とんでもない回数動くので、結局 RL のようになっている地点でずっとループすることになる。
問題は、「各マスにいた子供たちがたどり着くことになる RL な地点で、 最終的に R で止まるのか？ L で止まるのか？」ということ。
これらは、そこにたどり着くまでの距離の偶奇で決まる。逆に言えば、左側に続く連続するR の数と、 右側に続く L の数がわかれば、 RL となっている地点で、どちらにどのぐらい割り振られるかがわかる。

こんな図のイメージです。

解法イメージ

実装

リストや文字列を反転させて考えると、 R についてと L についての実装をほとんど同じにできて楽。

S = input()
N = len(S)

ans = [0] * N

# RL となっているようなRについて、左側に連続するRの数を数えていく
cnt = 0
for i, s in enumerate(S):
    if s == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i - 1] += (cnt + 1) // 2
        cnt = 0

cnt = 0
ans = ans[::-1]

# RL となっているようなLについて、右側に連続するLの数を数えていく
for i, s in enumerate(S[::-1]):
    if s == 'L':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i - 1] += (cnt + 1) // 2
        cnt = 0

print(*ans[::-1], sep=' ')

感想

割と好きな問題。 反転させて実装を楽にするテクニックは便利ですね。