🎃

ABC 254 C - K Swapのメモ

2022/10/04に公開

AtCoder

競プロ

tech

目についたC問題を解いてみようとしたけど全然解けなかった回です。

考えたこと

Kが1のときは確実にソート可能というのは気づいたものの、Kが2以上の場合は実際に入れ替えてみる解法しか思いつきませんでした。
（その前に意味わからんコードを提出したりもしてますが…）

import java.util.Collections

fun main() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val a = listOf(0).plus(readLine()!!.split(" ").map { it.toInt() }).toMutableList()

    if(k == 1) {
        a.sort()
    } else {
        var copyA: List<Int>
        do {
            copyA = a.toList()
            for(i in 1..(n - k)) {
                if(a[i] > a[i+k]) {
                    Collections.swap(a, i, i+k)
                }
            }
        } while(a != copyA)
    }
    if(a == a.sorted()) {
        println("Yes")
    } else {
        println("No")
    }
}

当然TLEです。

解説を見て

Aの添字をKで割った余りが一致するものごとに分けて、それぞれをソートするということでした。
入れ替えはそのグループ内でしか発生せず、交わることがないので独立してソート可能だと。言われてみれば確かにという感じですが、自力では気づけませんでしたね。
独立してそれぞれソートするとしても、遅いアルゴリズムでソートしても意味がないので高速なアルゴリズムを使うということですね。
上記のTLEになる解法も結果的にはソートしてることになりますが、これってバブルソートじゃない？って気づいていれば発想できたのでしょうか。バブルソートは知っていますが、これがそうであると気づかなかったのは不覚です。

計算量の削減は、シミュレーションせず計算によって求めるパターンと、シミュレーションはするけど操作回数を少ない方法をとるパターンに分けられると思いますが、今回は後者でしたね。
実際にはソートせずに計算で判定する方法があるのかなと考えていましたが、まさか実際にソートする解法だったとは…

fun main() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    for(i in 0 until k) {
        val b = mutableListOf<Int>()
        for(j in i until n step k) {
            b.add(a[j])
        }
        b.sort()

        for(j in i until n step k) {
            a[j] = b[j/k]
        }
    }

    if(a == a.sorted()) {
        println("Yes")
    } else {
        println("No")
    }
}

何気に実装も難しい気がします。添字の操作は難しい。なかなか心折れそうになる回でした…ｗ

その他

ところで、転倒数を求めるためにバブルソートを使う回とかもあったんですよね。Twitterで「バブルソート」がトレンド入りしていたので覚えています。実はバブルソートって頻出なのでしょうか？

考えたこと

解説を見て

その他

Discussion