ABC158 D - String Formation

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    s = sys.stdin.readline().rstrip()
    Q = int(sys.stdin.readline().rstrip())
    m = ""
    u = ""
    r = 0
    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            m, u = u, m
            r ^= 1
        elif line[0] == '2' and line[1] == '1':
            m += line[2]
        else:
            u += line[2]

    if r == 0:
        print(m[::-1] + s[::1] + u)
    else:
        print(m[::-1] + s[::-1] + u)


if __name__ == '__main__':
    main()

考え方

単純にクエリを条件通りに処理すると、
文字列の反転処理などに時間がかかるため、LTEとなる。

例：Submission #10645866 - AtCoder Beginner Contest 158

そのため、工夫が必要。
まず、先頭の文字列（上記コードではm）と末尾の文字列（上記コードではu）用の変数を用意し、
F = 1の時はm、F = 2の時はuに文字列を追加する。
大切なのはT = 1のとき、
先頭の文字列と末尾の文字列を入れ替えること、反転状態の有無を保持しておくこと。
配列を用意し、reverseを使用すると時間がかかるため、単純に変数を入れ替えることで
反転の処理を行う（コード上のm, u = u, m）

最後に、 反転していない状態であれば、初期の文字列Sとm、uをつなげて出力
反転している状態であれば、初期の文字列Sを反転させ、mとuをつなげて出力。

ちなみに、最後のprint文で先頭の文字列(m)のみ、[::-1]で反転させている理由は、
先頭の文字列と末尾の文字列を入れ替えたとき、
先頭から末尾の入れ替えは自動的に文字列が反転された状態になるが、
末尾から先頭の入れ替えは末尾の文字列が反転されていない状態で先頭にくるため。

実際の操作例

input

a
6
2 2 a
2 1 b
1
2 2 c
1
1
  • 操作０：m: '' s: 'a' u: ''
  • 操作１：m: '' s: 'a' u: 'a'
  • 操作２：m: 'b' s: 'a' u: ''
  • 操作３：m: 'a' s: 'a' u: 'b'
  • 操作４：m: 'a' s: 'a' u: 'bc'
  • 操作５：m: 'bc' s: 'a' u: 'a'
  • 操作６：m: 'a' s: 'a' u: 'bc'