ABC158D String Formation

問題

https://atcoder.jp/contests/abc158/tasks/abc158_d

方針

愚直に支持された通りにシミュレーションを行う。

ポイント

Pythonのlistは末尾への要素追加をappendでO(1)のコストで行えますが、
先頭への要素追加insertはO(n)のコストがかかってしまいます。

そこで、両端キューを使います。

Pythonの両端キューは標準ライブラリdequeとして実装されています。

両端キューは要素の追加が、先頭・末尾ともにO(1)のコストで行えます。

メモ

dequeにはreverseメソッドが存在するのですが、
これを利用した場合TLEとなってしまったので、
自前でdequeの方向を管理することにしました。

コード

from collections import deque
d = deque()
s = input()
d.append(s)
rev = 0 # dequeの方向を記録。0なら通常、1なら逆向きを表す。
Q = int(input())
for q in range(Q):
    op = input().split()
    if op[0] == '1':
        rev = (rev + 1) % 2
    else:
        if (int(op[1]) + rev) % 2 == 0: # dequeの向きを考慮してどちらに追加するか分岐
            d.append(op[2])
        else:
            d.appendleft(op[2])
ans = ''.join(list(d))
if rev == 1: # dequeが逆向きなら最後に戻す
    ans = ans[::-1]
print (ans)

記事情報

• 投稿日：2020年3月7日
• 最終更新日：2020年3月7日