【pythonでZONE2021を解説】D - Message from Aliens

問題概要

問題ページ

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\) の末尾に加える。
• この操作の後、\(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()