AtCoder-ABC199 C - IPFL【Python解答例】

AtCoder Beginner Contest199のC - IPFLについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 199（Sponsored by Panasonic） - AtCoder

AtCoder Beginner Contest199 C - IPFL

C - IPFL

問題文

長さ 2N の文字列 S があります。
この文字列に対して Q 個のクエリが与えられます。i 番目のクエリでは 3 つの整数 Ti,Ai,Bi が与えられるので、以下の処理をします。

・Ti=1 のとき : S の Ai 文字目と Bi 文字目を入れ替える
・Ti=2 のとき : S の前半 N 文字と後半 N 文字を入れ替える(Ai,Bi の値は用いない)
例えば S が FLIP のときにこのクエリを処理すると、S は IPFL となる。
これら Q 個のクエリを与えられた順に全て処理した後の S を出力してください。

制約

・1≤N≤2×10^5
・S は長さ 2N の英大文字のみからなる文字列
・1≤Q≤3×10^5
・Ti は 1 または 2
・Ti=1 のとき、1≤Ai

解答例

n = int(input())
s = input()
q = int(input())

T = []
A = []
B = []
for i in range(q):
    t, a, b = map(int,input().split())
    T.append(t)
    A.append(a)
    B.append(b)

# 文字列を前半と後半に分割
S1 = list(s[:n])
S2 = list(s[-n:])

# 前半後半の入れ替え回数
num = 0

for i in range(q):
    if T[i] == 1:
        # Ai文字目をtmp1に記憶
        if num % 2 == 0 and A[i]-1 < n:
            tmp1 = S1[A[i]-1]
        if num % 2 == 0 and A[i]-1 >= n:
            tmp1 = S2[A[i]-1-n]
        if num % 2 == 1 and A[i]-1 < n:
            tmp1 = S2[A[i]-1]
        if num % 2 == 1 and A[i]-1 >= n:
            tmp1 = S1[A[i]-1-n]
        # Bi文字目をtmp2に記憶
        if num % 2 == 0 and B[i]-1 < n:
            tmp2 = S1[B[i]-1]
        if num % 2 == 0 and B[i]-1 >= n:
            tmp2 = S2[B[i]-1-n]
        if num % 2 == 1 and B[i]-1 < n:
            tmp2 = S2[B[i]-1]
        if num % 2 == 1 and B[i]-1 >= n:
            tmp2 = S1[B[i]-1-n]

        #記憶したtmp1をBi文字目に代入
        if num % 2 == 0 and B[i]-1 < n:
            S1[B[i]-1] = tmp1
        if num % 2 == 0 and B[i]-1 >= n:
            S2[B[i]-1-n] = tmp1
        if num % 2 == 1 and B[i]-1 < n:
            S2[B[i]-1] = tmp1
        if num % 2 == 1 and B[i]-1 >= n:
            S1[B[i]-1-n] = tmp1
        #記憶したtmp2をAi文字目に代入
        if num % 2 == 0 and A[i]-1 < n:
            S1[A[i]-1] = tmp2
        if num % 2 == 0 and A[i]-1 >= n:
            S2[A[i]-1-n] = tmp2
        if num % 2 == 1 and A[i]-1 < n:
            S2[A[i]-1] = tmp2
        if num % 2 == 1 and A[i]-1 >= n:
            S1[A[i]-1-n] = tmp2

    # 前半後半の入れ替え回数を更新
    if T[i] == 2:
        num += 1

# 入れ替え回数に応じて順序変更
if num % 2 == 0:
    ans = "".join(S1) + "".join(S2)
else:
    ans = "".join(S2) + "".join(S1)
print(ans)

解説

指示された通りの処理を行った場合の文字列を答える問題です。

問題文の通りに忠実に処理を行うと制限時間に間に合いません。
文字列の前半後半の入れ替えはクエリの処理中には行わず、最後に入れ替え回数に応じて順序を入れ替えることで対応しました。

スマートな条件分岐ができず、コードはゴリゴリの力技で解いています (-_-;)

Tiが1のとき、Aiの文字をtmp1に、Biの文字をtmp2に記憶させます。
tmp1はBiの位置に、tmp2をAiの位置に代入することで処理を行いました。
前半後半の入れ替え状況と、文字の位置によってそれぞれ4通り条件分岐させました。
お世辞にもいいコードとは言えずお恥ずかしいです (;^_^A

Tiが2のときは入れ替え回数のnumに1を足していきます。

ループを抜けたら前半と後半に分けた文字列を入れ替え回数numに応じた順序で結合させます。

結合させた文字列を出力すればOKでした！

続いてABC199のD問題も記事にしていきたいと思います。

ABC199の関連記事はこちら
ebisuke33.hatenablog.com