AtCoder ABC 158 D問題

Question

前提・実現したいこと

問題に正答したい

発生している問題・エラーメッセージ

一部サンプルがTLEになる

該当のソースコード

s = input()
q = int(input())
num = 0
ans = "0"

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans = query[2] + ans
      else:
        ans = ans + query[2]
    else:
      if num%2 == 0:
        # 後方
        ans = ans + query[2]
      else:
        ans = query[2] + ans
        
mes = ans.replace("0", s)
if num%2 == 0:
  print(mes)
else:
  print(mes[::-1])

試したこと

解説にある通り、forループ中では反転を行わずに最後に反転して計算量を削減する工夫をしました。

Answer 1

ABC 158 解説

ここで、C + + などで普通の文字列型の先頭に追加する操作は計算量が悪いため、deque で文字列

を管理するか、左右で分けて文字列を保持し最後に適切に連結するといった方法で対処できます。

と記述あるようにPythonでも文字列のまま処理するとTLEになります。
たとえばdeque オブジェクトを使うと通ります。