🙆‍♀️

ABC199 C - IPFLのメモ

2022/11/19に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。今回はあまり難しくなさそうなのを選びました。

考察

以前似たような問題を見たことがあります。

$Ti = 2$ のときのSの前半N文字と後半N文字を入れ替える操作を実際に行うとおそらく間に合わないので、入れ替えが発生したことがわかる情報だけ記録して、実際の入れ替えは出力時の1回だけ行えばいいです。
文字列は環状につながっていて、入れ替えとはどこを先頭と見なすかが変わるだけと考えることができます。
たとえばFLIPに対して入れ替えを行うとIPFLになりますが、FLIPという文字列自体は変わらずに先頭と見なす個所がN+1番目に移ったと考えると、文字列の先頭はIになります。そして文字列は環状につながっているとすると、PのうしろにFLがあるということになりますので、そこから読んでいくとIPFLになります。このように実際に入れ替えた場合と同じ文字列が得られます。

この問題の場合は文字列の先頭としてあり得るパターンがSの1番目とN+1番目の2パターンしかありませんので、真偽値だけで表現できます。

なお $Ti = 1$ の時の入れ替えのほうですが、これは軽い処理だと思うので実際に行なっていいと思います。
ただし、文字列の先頭がN+1番目になっている場合は補正する必要があります。

実装

import java.io.PrintWriter
import java.util.Collections

fun main() {
    val n = readLine()!!.toInt()
    val s = readLine()!!.toMutableList()
    val q = readLine()!!.toInt()

    var swapped = false
    repeat(q) {
        val (t, a, b) = readLine()!!.split(" ").map { it.toInt() }

        if(t == 1) {
            if(swapped) {
                Collections.swap(s, (a+n-1) % (2*n), (b+n-1) % (2*n))
            } else {
                Collections.swap(s, a-1, b - 1)
            }
        } else if(t == 2) {
            swapped = !swapped
        }
    }

    val out = PrintWriter(System.out)
    if(swapped) {
        for(i in n until (2*n)) {
            out.print(s[i])
        }
        for(i in 0 until n) {
            out.print(s[i])
        }
    } else {
        s.forEach {
            out.print(it)
        }
    }
    out.println()
    out.flush()
}

文字列の先頭がどこかというのは、実質的には入れ替わっている状態かどうかだけ考えればいいのでswappedというBooleanの変数で管理します。

$Ti = 1$ の操作を実際に実行するため、文字列は可変の配列として扱っています。
入れ替わっている場合の補正ですが、基本はAとBそれぞれにNを足した値同士で入れ替えればいいのですが、単純に実行すると範囲外になる可能性があります。その場合、はみ出た分は実際の先頭から引き続き数えればOKです。これはmodを使って表現できます。文字列の長さが $2N$ なので、それでmodをとります。
-1があるのは0-indexedだからです。ここは事前に補正したほうがよかったかもしれません。

最後に、入れ替わっていない状態なら単純に前から出力するだけ、入れ替わっていたら後半N文字を先に出力してから前半N文字を出力すればOKです。

考察

実装

Discussion