ABC199 C問題 IPFL を解く - 競技プログラミング悪戦苦闘日記

ABC199 C問題 IPFLを解説しつつ、ふりかえります。

問題

長さ 2N の文字列 S があります。
この文字列に対して Q 個のクエリが与えられます。
i 番目のクエリでは 3 つの整数 $T_i, A_i, B_i$ が与えられるので、以下の処理をします。
$T_i = 1$ のとき : S の $A_i$ 文字目と $B_i$ 文字目を入れ替える
$T_i = 2$ のとき : S の前半 N 文字と後半 N 文字を入れ替える( $A_i, B_i$ の値は用いない)
例えば S が FLIP のときにこのクエリを処理すると、S は IPFL となる。
これら Q 個のクエリを与えられた順に全て処理した後の S を出力してください。

難しいところ

ダメダメな私は計算量がだめかもと思いつつ、dequeとか使って素直に問題の通りの処理を実装して、時間制限を超えました。
クエリの数が最大で $3 \times 10^5$ 、文字の長さが最大で $4 \times 10^5$ になるので、 $T_i =2$ の前半と後半の入れ替え処理で素直にループすると無理なんですよね。。。
そして最後まで良い知恵が思いつきませんでした。。。

解く時のイメージ

前半と後半を入れ替える処理は、偶数回入れ替えたら、元の文字列になります。
問題なのは、前半と後半が入れ替わった時に、インデックス指定で文字を入れ替える時です。
なので、その処理の時だけ前半後半の入れ替えが発生しているかどうかを勘案して、インデックスをひねってから文字を入れ替えます。
あとは最後に入れ替わっているかの状態を見て、前半と後半を入れ替えてから文字列を出力する、あるいはそのまま出力します。

具体的な解き方

まずは、前半と後半を入れ替える処理についてはフラグで文字列の状態を管理します。なので、 $T_i =2$ の時はこのフラグを反転させるだけにします。
例えば、奇数回入れ替えが発生してたら、フラグをTrueにします。

文字を入れ替える処理の時は、この前半後半の入れ替えが発生していることを考慮します。
インデックスが前半にあったら、長さが2Nなので、Nだけ足します。
インデックスが後半にあったら、Nだけ引きます。
例えば、4文字の長さだったら、前半と後半の入れ替えで、インデックスは0 -> 2、1 -> 3、2 -> 0、3 -> 1になります。
その後に指定されたインデックスの位置の文字を入れ替えます。

その操作をクエリの数だけ繰り返して、最後に入れ替えフラグを見て、入れ替わっているようなら前半と後半を入れ替える処理をします。
ここはループの外なので計算量のオーダーが文字列の長さと等しくても大丈夫です。

以下のコードになりました。

N = int(input())
S = list(input())
Q = int(input())

flip_flag = False

for i in range(Q):
    t, a, b = map(int, input().split())
    if t == 1:
        # 前半後半が反転しているケース
        if flip_flag:
            # aとbのインデックスが前半にあるか判定してNを足すか引くか決める
            a_idx = a - 1 - N
            if a - 1 < N:
                a_idx = a - 1 + N
            b_idx = b - 1 - N
            if b - 1 < N:
                b_idx = b - 1 + N
            S[a_idx], S[b_idx] = S[b_idx], S[a_idx]
            continue
        # 前半後半が反転していないケース
        S[a - 1], S[b - 1] = S[b - 1], S[a - 1]
        continue
    # t == 2の時は前半後半が反転しているかどうかの状態を変更するだけ
    flip_flag = not flip_flag

# 最後に前半後半が反転しているかどうかで、反転させるか決める
if flip_flag:
    newS = "".join(S[N:] + S[:N])
    S = newS

ans = "".join(S)
print(ans)