【ABC158 D】「String Formation」を解く【Python3】

高橋君が持っている文字列Sから初めて、手順に従って最終的にできた新しい文字列を答える問題です。

工夫すれば、愚直にコードを書いてもACできます。

が、今回はcollectionsモジュールの「deque」を知っていると、時間短縮することができます。

リストでは、先頭に要素を追加・削除する際に、O(n)の時間コストを必要としますが、dequeを使うと、O(1)で実行できます。

今回のように、両端に要素を挿入する場合に重宝しますね。

提出

from collections import deque
s = deque(input())
q = int(input())
li = [list(map(str, input().split())) for _ in range(q)]

flag = True

for i in range(q):
    que = li[i]
    if que[0] == "1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        f = que[1]
        c = que[2]
        if flag:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)

if flag:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))

T_i=1のときに毎回前後反転していては、コストがかかるので、正順のときに「True」、逆順のときに「False」となるように、flagを毎回定めます。

以降は、flagが「Trueかどうか」を判定して、操作を実行します。

Trueであれば、先頭と末尾への処理は問題文の通りですが、Falseであれば、反対の処理をします。

最後も、Falseのときには全体を反転してから出力します。

余談ですが、「deque」を知らなかった自分は、コンテスト本番で、下のように書きました。

提出

s = input()
q = int(input())
li = [list(map(str, input().split())) for _ in range(q)]

moji = "0"
flag = True

for i in range(q):
    que = li[i]
    if que[0] == "1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        f = que[1]
        c = que[2]
        if flag:
            if f == "1":
                moji = c + moji
            else:
                moji = moji + c
        else:
            if f == "1":
                moji = moji + c
            else:
                moji = c + moji

if flag:
    print(moji.replace("0", s))
else:
    moji = moji[::-1]
    print(moji.replace("0", s[::-1]))

文字列に「0」を当てて、最後に文字列Sに置き換える方法で解いています。

実行時間が「1997ms」と本当にギリギリなので、運が良かったと思います。