📖

ABC289 E - Swap Placesのメモ

2023/02/23に公開

AtCoder

競プロ

tech

以前コンテストで見たけど解けなかった問題について、既存のACコードを見て若干わかったような気になったのでメモです。
（今回は本当にメモレベル）

メモ

高橋君と青木君を同時に考えずに片方だけについて考えるなら、頂点1と頂点 $N$ が連結であれば二人とも到達自体は可能です。なのでグラフを走査するのはわかりますが、実際にはそれだけでなく最短経路を辿る必要があるのと、二人の移動先の頂点が異なる必要があること、あとは計算量の考慮などが必要になります。

強い人のコードを真似た実装を先に見てみます。

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        val c = listOf(0) + readLine()!!.split(" ").map { it.toInt() }

        val graph = Array(n + 1) { mutableListOf<Int>() }
        repeat(m) {
            val (u, v) = readLine()!!.split(" ").map { it.toInt() }
            graph[u].add(v)
            graph[v].add(u)
        }

        val queue = java.util.ArrayDeque<Pair<Int, Int>>()
        queue.add(1 to n)

        val steps = Array(n + 1) { IntArray(n + 1) { -1 } }
        steps[1][n] = 0

        while (queue.isNotEmpty()) {
            val (takahashi, aoki) = queue.removeFirst()

            val step = steps[takahashi][aoki]
            for(nextTakahashi in graph[takahashi]) {
                for(nextAoki in graph[aoki]) {
                    if(c[nextTakahashi] == c[nextAoki]) {
                        continue
                    }
                    if(steps[nextTakahashi][nextAoki] != -1) {
                        continue
                    }

                    steps[nextTakahashi][nextAoki] = step + 1
                    queue.add(nextTakahashi to nextAoki)
                }
            }
        }
        println(steps[n][1])
    }
}

結果としては実装的には計算量をあまり考慮する必要はなく、単純に二重にBFSすればよかったようです。正確には理解してないと思いますが、単純に計算するといかにもダメそうな数値が出ますが。実際には色の制約により絞られるのでセーフ、ととりあえず認識しました。

まあ計算量について理解していれば解けたかというと、たぶん解けませんでした。「単純に二重にBFS」とか書きましたが、意外と実装できない。
頂点はPairで管理し、二重ループする。色の制約は色が同じだったら遷移しないようにすればよく、あとは steps で最小ステップ数を管理するだけ。（訪問済かどうかのチェック用情報も兼ねる）

自力でこんなにシンプルに書く方法は思いつかないですね。

ちなみに参考にしたのはこちらです。

強い人は本当に強い…

（執筆時間: 18分58秒）

メモ

Discussion