AtCoder ABC136

概要

AtCoderの記録です。全部Pythonで頑張ります。

この記事の対象

• AtCoderについてある程度知っている人
• Pythonがわかる人

本編

AtCoderとは

競技プログラミングコンテストを開催している会社です。 atcoder.jp

ABC136

20時くらいにうとうとしてしまって目が覚めたら23時でした。
不参加。後からDだけ解きました。

D Gathering Children

RLという２文字の組み合わせに至った子供達は永遠にここの二つをさまようことになります。 移動が10¹⁰⁰と非常に大きい回数繰り返されるので、どの子どももRLという二文字の場所のどれかに収束すると考えてよいです。

あるRLに注目してみると、この吸収ゾーンに収束する子供の数は、「RLのRの左に連続して続くRの数」+「RLの右に連続して続くLの数」+２（RLにはじめにいた子供二人）となります。

例えば…LRRRLLLLLR…なら8人の子供が真ん中のRLに収束します。

まず連続するRにいた人の収束場所を考えてみます。
10¹⁰⁰は偶数なので、…RRRRRRRL…という例で考えてみると、青文字のRにいた人は緑文字のRに、赤文字のRにいた人は黄文字のLに収束することがわかります。

…RRRRRRRL…

連続するLに関しては、Sを左右反転させて、LをRに、RをLに変えると、さっき考えたRの操作と同等です。

すなわち、コードは以下のようになります。

S = input()

N = len(S)
ans = [0 for i in range(len(S))]
R_cnt = L_cnt = 0

for i in range(N):
    if S[i] == 'R':
        if S[i+1] == 'L':
            ans[i] += R_cnt//2 + 1
            ans[i+1] += R_cnt//2 + 1
            R_cnt = 0
        else:
            R_cnt += 1

for i in range(N):
    if S[N-i] == 'L':
        if S[N-(i+1)] == 'R':
            ans[N-i] += L_cnt//2 + 1
            ans[N-(i+1)] += L_cnt//2 + 1
            L_cnt = 0
        else:
            L_cnt += 1

L = [str(int(i)) for i in ans]
print(' '.join(L))

N回ループが２つあります。１つ目は連続するRについての操作、２つ目は連続するLについての操作です。

まとめ

不参加なのでレート変わらずです。
院試頑張ります！