ZONe2021 D問題 宇宙人からのメッセージ の解説とふりかえり

ZONe2021 D問題 を解説します。

atcoder.jp

問題

暗号文 S が与えられます。この暗号文は、以下の操作で解読することが出来ます。

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

難しいポイント

暗号文の長さが なので、反転の操作をそのまますると計算量が文字の長さ分かかるので、タイムアウトします。
2文字連続する文字を除くのも実直に探索すると文字列の長さの分だけ計算量がかかるので、この操作も工夫が必要です。

解き方の方針

反転の操作はその場で操作するのではなくて、反転した状態かどうかをフラグで記録しておきます。
答えを出力手前で反転していれば、反転して出力します。
文字を末尾につける操作の時も、反転した状態の場合は末尾ではなくて先頭につけます。

2文字連続する文字を除く操作については、文字を加えるときに末尾の文字と加えようとしている文字が同じ場合は2文字続いてしまうので、末尾の文字を取り除きます。

操作対象のTはcollections.dequeで定義しておきます。先頭への追加がO(1)の計算量で済みます。

最近解いたC - IPFLに近い問題だと思いました。

実装方法

実装方法で特別なことはないです。
Tの長さが0のときは有無を言わせず文字を追加して、continueしてすぐに次のループに入ってます。
早期リターンのノリで for 文の中で早期continueする書き方が自分の好みです。
continueの後の処理を書くときに、全段のif文の条件式のことを考慮しなくて済みます。
ここだと長さ0のif文を最初に持ってきて処理してcontinueしているので、その後の処理では長さ0という条件を考慮に入れる必要はありません。

from collections import deque

S = input()
flip_flag = False
T = deque()

for s in S:
    # フラグを反転させるだけ
    if s == 'R':
        flip_flag = not flip_flag
        continue
    # 長さ0なら最後に追加する
    if len(T) == 0:
        T.append(s)
        continue
    # 反転した状態で操作する
    if flip_flag:
        # 付け足すことで同じ文字が連続しそうなら削除する
        if T[0] == s:
            T.popleft()
        else:
            T.appendleft(s)
    # 反転してない状態で操作する
    else:
        # 付け足すことで同じ文字が連続しそうなら削除する
        if T[-1] == s:
            T.pop()
        else:
            T.append(s)

# 最後に反転した状態なら反転させる
if flip_flag:
    T.reverse()
print("".join(T))

C問題が400点でD問題が300点の理由がわかった気がします。
文字列操作の練習として、私にはちょうどいい問題のような気がしました。