文系独学プログラマーの仕訳帳

  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ
  1. HOME >
  2. Edit >

Edit

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

2022年1月24日

問題概要

問題ページ

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()

プログラミング

  • TwitterTwitter
  • Share Share
  • PocketPocket
  • Hatena Hatena
  • LINE
  • コピーする

-Edit
-deque, ABC-Like-D

author

関連記事

no image
【pythonでABC179を解説】F - Simplified Reversi
no image
【pythonでABC175を解説】E - Picking Goods
no image
【pythonでABC203を解説】A - Chinchirorin
no image
【pythonでABC175を解説】B - Making Triangle
no image
【pythonでABC151を解説】D - Maze Master
no image
【pythonでABC169を解説】C - Multiplication 3
no image
【pythonでABC195を解説】E - Lucky 7 Battle

【pythonでZONE2021を解説】C - MAD TEAM

【pythonでABC200を解説】A - Century

たびすけ

東証1部上場企業の社畜
プログラミングとブログが趣味
勉強好きの怠け者
プログラミングを独学

サイト内検索

カテゴリ

最近のつぶやき

Tweets by XXXHOLiC_xxx
  • ブログ
  • プログラミング
    • python
    • Excel
    • データベース
  • 競技プログラミング
    • AtCoder Beginner Contest
  • カナヘビ
  • 雑記
  • Edit

タグ

ABC-A (68) ABC-B (55) ABC-C (43) ABC-D (37) ABC-E (21) ABC-F (11) ABC-Like-A (1) ABC-Like-B (1) ABC-Like-C (1) ABC-Like-D (1) BitDP (2) deque (3) DP (1) heapq (1) imos法 (1) n進数 (1) Union Find (3) Zアルゴリズム (1) セグメントツリー (2) ダイクストラ法 (1) トポロジカル (1) メモ化再帰 (3) レッドローチ (1) ワーシャルフロイド (1) 二分探索 (2) 幅優先探索 (2) 深さ優先探索 (1) 素数 (1) 組み合わせ (3) 論理演算 (4)
  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ

文系独学プログラマーの仕訳帳

© 2022 文系独学プログラマーの仕訳帳