🐡

ABC219 C - Neo-lexicographic Orderingのメモ

2023/03/30に公開

AtCoder

競プロ

tech

なんとなくやってみた問題でハマったのでメモです。大した内容ではないですが、一応提出コードから直接的には読み取れない情報なので書いておきます。

この問題は考察というほどのことは必要なく、各英小文字について入力順に対応した数値をマッピングしてその数値でソートされるようにするだけです。JavaとかKotlinならComparatorを実装するとかします。

最初に提出したのはこれです。

import kotlin.math.min

fun main() {
    val x = readLine()!!
    val n = readLine()!!.toInt()
    val s = List(n) {
        readLine()!!
    }

    val map = mutableMapOf<Char, Int>()
    x.toList().forEachIndexed { index, c -> map[c] = index }

    val charComparator: Comparator<Char> = compareBy { map[it]!! }
    val strComparator = Comparator<String> { s1, s2 -> rec(charComparator, s1, s2, 0) }

    s.sortedWith(strComparator).forEach { println(it) }
}

private fun rec(comparator: Comparator<Char>, s1: String, s2: String, i: Int): Int {
    val cmp = comparator.compare(s1[i], s2[i])
    if(min(s1.length, s2.length) == i + 1) {
        return cmp
    }

    if(comparator.compare(s1[i], s2[i]) != 0) {
        return cmp
    }

    return rec(comparator, s1, s2, i + 1)
}

REが出ました。

配列外参照、mapから取得できなくてぬるぽ、再帰の階層が深くてスタックオーバーフローなどを疑ったもののどれも違いました。

ローカルでテストデータをランダム生成して動かして、実際にはこのようなエラーが出ることがわかりました。

java.lang.IllegalArgumentException: Comparison method violates its general contract!

比較関数の契約違反… 要するに比較関数の返す結果に矛盾があるので正常なソートができないというエラーです。
REの原因について上で挙げたのが全部違うならまあこれだろうと薄々思ってはいましたが、なんでそうなるのかわからなかったので実際見るまでは半信半疑でした。

で、再現した時のテストデータを見たら原因がわかりました。上記の実装だと、以下の2つのような長さが異なる文字列で、長さが短い方が長い方の前方と完全に一致するケースで、その2つを「同じ」と判定してしまいます。

abc
abcd

問題なのはこの箇所。

    val cmp = comparator.compare(s1[i], s2[i])
    if(min(s1.length, s2.length) == i + 1) {
        return cmp
    }

$i$ をインクリメントしながら1文字ずつ比較していって、長さが短いほうの文字列の末尾まで来た場合ですね。その1つ前までは一致しているので最後の文字の比較結果を最終結果とするという実装ですが、上記の通りです。

うーん、ひどい。まあ原因はわかったので修正です。

import kotlin.math.min

fun main() {
    val x = readLine()!!
    val n = readLine()!!.toInt()
    val s = List(n) {
        readLine()!!
    }

    solve(x, s)
}

fun solve(x: String, s: List<String>) {
    val map = mutableMapOf<Char, Int>()
    x.toList().forEachIndexed { index, c -> map[c] = index }

    val charComparator: Comparator<Char> = compareBy { map[it]!! }
    val strComparator = Comparator<String> { s1, s2 ->
        rec(charComparator, s1, s2, 0)
    }

    s.sortedWith(strComparator).forEach {
        println(it)
    }
}

private fun rec(comparator: Comparator<Char>, s1: String, s2: String, i: Int): Int {
    //println("s1=$s1 s2=$s2")
    if(min(s1.length, s2.length) - 1 == i) {
        val cmp = comparator.compare(s1[i], s2[i])
        return if(cmp != 0) {
            cmp
        } else {
            if(s1.length == s2.length) {
                0
            } else if(s1.length < s2.length) {
                -1
            } else {
                1
            }
        }
    }

    val cmp = comparator.compare(s1[i], s2[i])
    if(cmp != 0) {
        return cmp
    }

    return rec(comparator, s1, s2, i + 1)
}

短い方の最後までは一致しているけど全体としては異なる場合は長い方が後と判定します。

（実際には原因がわかるまでの間に提出デバッグしまくってたのでペナルティを量産していましたが…深夜テンションでおかしかったので許してもろて）

（執筆時間: 30分28秒）

Discussion