ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

ZONeエナジー プログラミングコンテスト D - 宇宙人からのメッセージ【Python解答例】

f:id:ebisuke33:20210502004824p:plain

ZONeエナジー プログラミングコンテストのD問題についてPythonの解答例を記事にしていきます。
atcoder.jp



ZONeエナジー プログラミングコンテスト D - 宇宙人からのメッセージ

D - Message from Aliens

問題文

暗号文 S が与えられます。この暗号文は、以下の操作で解読することが出来ます。
T を空文字列とする。i=1,2,…,|S| について、順番に以下を行う。 (|S| は S の長さを表す)S の i 文字目が R のとき、T を反転させる。
S の i 文字目が R でないとき、その文字を T の末尾に加える。
この操作の後、T の中に同じ文字が 2 つ連続で並んでいたら、その 2 文字を取り除く。この操作を出来る限り続ける。 (最終的に得られる文字列は取り除く順番によらないことが証明できる)
この操作で得られる文字列 T を出力してください。

制約

・S は英小文字と R からなる
・1≤|S|≤5×10^5

解答例

from collections import deque

s = input()

que = deque()

# 反転フラグ
rev = False

for i in range(len(s)):
    # 文字がRならフラグ反転
    if s[i] == "R":
        rev = not rev
    
    # 反転フラグtrueの場合
    elif rev:
        if len(que)>0 and que[0] == s[i]:
            que.popleft()
        else:
            que.appendleft(s[i])
    # 反転フラグFalseの場合
    else:
        if len(que)>0 and que[-1] == s[i]:
            que.pop()
        else:
            que.append(s[i])

# 反転フラグTrueなら文字列反転
if rev:
    que = reversed(que)
    
print("".join(que))

解説

与えれらる文字列Sに指定された操作を行ったあとに得られる文字列Tを答える問題です。
公式解説にそった解答例です。

キューを用いて文字列を操作し、反転状況については反転フラグrevを用いて管理します。

文字列Sを先頭から順に確認して操作していきます。
Rが出たときは反転フラグrevを反転させます。
R以外のときはrevによって操作を変更します。

revがTrueのときはqueの左端に注目し、左端と調べている文字が一致していればqueの左端を削除します。
一致していなければqueの左端に文字を足していきます。

revがFalseの場合は先ほどと異なり右端に注目し、削除や追加は右端になります。

このループが抜けた後、revがTrueならqueを反転させます。

最後にqueを順番につなげて文字列を出力すればOKでした。



ZONeエナジー プログラミングコンテストの関連記事はこちら
ebisuke33.hatenablog.com