問題概要
問題ページ
-
D - Message from Aliens
問題ページへ移動する
ストーリー
\(1\) 週間後、選りすぐりのプログラマ達が集まった。みなそれぞれに MAD なスキルを持つ曲者揃いだ。
早速 UFO との直接対決を開始しよう。
ずっとメッセージを送り続けているにもかかわらず放置されている UFO は心なしか少しイラついているように見える。
急いで UFO からのメッセージを解読しなければ。
問題文
暗号文 \(S\) が与えられます。この暗号文は、以下の操作で解読することが出来ます。
- \(T\) を空文字列とする。
- \(i = 1, 2, \dots, |S|\) について、順番に以下を行う。 (\(|S|\) は \(S\) の長さを表す)
- \(S\) の \(i\) 文字目が
R
のとき、\(T\) を反転させる。 - \(S\) の \(i\) 文字目が
R
でないとき、その文字を \(T\) の末尾に加える。
- \(S\) の \(i\) 文字目が
- この操作の後、\(T\) の中に同じ文字が \(2\) つ連続で並んでいたら、その \(2\) 文字を取り除く。この操作を出来る限り続ける。 (最終的に得られる文字列は取り除く順番によらないことが証明できる)
この操作で得られる文字列 \(T\) を出力してください。
制約
- \(S\) は英小文字と
R
からなる - \(1 ≤ |S| ≤ 5 \times 10^5\)
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
s = str(input().rstrip('\n'))
is_r = False
ans = collections.deque()
for v in s:
if v == "R":
is_r = not is_r
else:
if not is_r:
if len(ans) == 0 or ans[-1] != v:
ans.append(v)
else:
ans.pop()
else:
if len(ans) == 0 or ans[0] != v:
ans.appendleft(v)
else:
ans.popleft()
if is_r:
ans.reverse()
print("".join(ans))
if __name__ == '__main__':
solve()