🙆‍♀️

ABC250 C - Adjacent Swapsのメモ

2023/01/04に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

考察

まずは愚直な実装を考えます。
$a_1,\dots,a_N$ となる配列を作って、実際に入れ替え操作を行なっていけばいいでしょう。初期値は1から始まって $N$ まで1ずつ増えた値です。

$x_i$ が $Q$ 回入力されるので、都度探索して位置を見つけて入れ替えを行います。位置が $N$ だったら左と、そうでなければ右と入れ替えます。

それが終わったら出力です。

ただ、これだと $x_i$ の探索がネックとなります。線形探索だと $O(N)$ なので、全体としては $O(N^2)$ となります。 $N$ の制約が $2 \times 10^5$ なのでこれでは間に合いません。

探索によって得たいのは $x_i$ の位置だけなので、それを別途保存して高速に問い合わせできれば解けそうです。
ボールに書かれた数値は重複もありませんし、単純に配列で位置情報を保持することができます。

実装

答えとなる数列はaで初期化して入れ替えを行います。1-indexedに補正するために先頭に0を入れます。

位置情報を保持するのはbucketです。これも1-indexedに補正するために1多く確保します。Kotlinの書き方について知らないと初期値がよくわからないと思いますが、要するに添字と同じ数値を値として初期値にしています。

import java.util.Collections

fun main() {
    val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    val xList = List(q) {
        readLine()!!.toInt()
    }

    val a = (0..n).toMutableList()

    val bucket = IntArray(n+1) { it }

    for(x in xList) {
        val i = bucket[x]
        if(i == n) {
            Collections.swap(a, i, i - 1)
            bucket[x] = i - 1
            bucket[a[i]] = i
        } else {
            Collections.swap(a, i, i + 1)
            bucket[x] = i + 1
            bucket[a[i]] = i
        }
    }
    println(a.subList(1, a.size).joinToString(" "))
}

あとは $x_i$ の位置をaを探索することによってではなく、bucketに問い合わせれば $O(1)$ で得ることができます。あとはaの入れ替えと、bucketの更新を行うだけです。

bucketの更新がちょっとわかりづらいかもしれません。bucket[x]は単純に入れ替え後の位置を記録するだけです。ただ、それだけでなく入れ替え対象のもう一方の値の位置情報も更新しないといけません。

位置情報を更新する対象は入れ替え前に右隣（もしくは左隣）にあった値ですが、それは入れ替え後には現在注目している位置にあります。なので、入れ替え後にa[i]が指している値が位置情報の更新対象です。
また、記録する位置は現在注目している位置です。

最後に出力ですが、1-indexedへの補正のために先頭に余分な値があるので、それは除いて出力します。
joinToString()と使うと全てを結合した大きな文字列を生成してしまうのですが、今回の問題くらいの制約ならそれでも問題ありません。

（執筆時間：17分35秒）

考察

実装

Discussion