• HOME
  • 競プロ
  • ブログ
  • 問い合わせ

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

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

Edit

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

2022年1月24日

問題概要

問題ページ

[st-card-ex url="https://atcoder.jp/contests/zone2021/tasks/zone2021_d" target="_blank" rel="nofollow" label="" name="" bgcolor="" color="" readmore="問題ページへ移動する"]

ストーリー

\(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
  • URLコピー

-Edit
-deque, ABC-Like-D

author

関連記事

no image
【pythonでABC197を解説】B - Visibility
no image
【pythonでABC005を解説】D - おいしいたこ焼きの焼き方
no image
【pythonでABC165を解説】C - Many Requirements
no image
【pythonでABC206を解説】A - Maxi-Buying
no image
【pythonでABC151を解説】D - Maze Master
no image
【pythonでABC054を解説】D - Mixing Experiment
no image
【pythonでABC178を解説】C - Ubiquity

【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
  • 競プロ
  • ブログ
  • 問い合わせ

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

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