📝

ABC204 C - Tourのメモ

2022/12/08に公開

AtCoder

競プロ

グラフ

tech

目についたC問題を解いてみるの回です。
解くのにすごく時間がかかりました。最初は解けそうで解けなくて、悔しいので解説は見ずにアルゴ式でグラフに慣れてから再挑戦して解きました。

考察

スタート地点からゴール地点への有向グラフとして考えることができます。探索してスタート地点とゴール地点のペアの個数を数えればいいのですが、スタート地点が一意に定まっていないのと、サイクルがあり得るのがポイントでしょうか。

たまたまなんですが、この問題に着手する前にもグラフを使って解ける問題を解いていました。

こちらと同じような感じで解けるのかなと思ったのですが、上記の問題はスタート地点を一意に定めることができたし、ゴール地点も明確で無限周回してしまうこともないので簡単だったようです。同じ考え方では解けませんでした。

スタート地点が決まっていないというのは、あり得るスタート地点を全部試す必要があるほか、「どこからスタートしたのか」という情報が重要になるということでもあります。たとえば1からスタートして2に到達した場合と、3からスタートして2に到達した場合を区別する必要があります。
またサイクルがありうるというのは、つまり同じところをぐるぐる回ってしまう可能性があります。そうならないようにガードを設ける必要がありますが、同じ地点に複数回到達したとしてもスタート地点が異なるのであれば探索を打ち切ってはいけないので、スタート地点と到達地点のペアで判定する必要があります。

実装

キューを使ってBFSで実装しました。（DFSでも解けますが）

スタート地点は1からNまであり得るので全部試します。三重ループになっていますが、制約が小さいので問題ありません。
探索済かどうかは visited で管理します。スタート地点と到達地点のペアで考える必要があるので二次元配列にしています。

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

    val graph = Array(n+1) { mutableListOf<Int>() }

    repeat(m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        graph[a].add(b)
    }

    val queue = java.util.ArrayDeque<Int>()

    var ans = 0

    val visited = Array(n+1) { BooleanArray(n+1) }

    for(from in 1..n) {
        queue.add(from)
        ans++
        visited[from][from] = true

        while(queue.isNotEmpty()) {
            val v = queue.poll()

            for(to in graph[v]) {
                if(!visited[from][to]) {
                    queue.add(to)
                    ans++
                    visited[from][to] = true
                }
            }
        }
    }

    println(ans)
}

ポイントは、途中経過は無視するってところですかね。たとえば1 -> 2 -> 3と繋がっているとして、1をスタート地点として探索している時はそれだけを考えます。途中経過としては2から3へ辿ったりしますが、この時は探索済としてマークせず、答えの件数としてもカウントしません。そのほうがシンプルになります。2をスタート地点として探索する時に網羅されるので漏れは発生しません。
最初はこの辺りで混乱してバグらせてました…

なお、制約が小さいのでループを抜けた後に visited を探索して件数を求めるようにすれば ans はなくてもいいかもしれません。

感想

いざ解けてみればそんなに難しくはないような気もしてきました。認識がもつれていたというかなんというか。ほどけてみればシンプルというか。アルゴ式で一からグラフについてやっていたらほどけたので、悩んでも解けなかったら結局基礎からやるのが結果的には早いのかもしれません。

これの3章までやってから再挑戦したら解けました。
https://algo-method.com/courses/19

4章以降もそのうちやると思います。

考察

実装

感想

Discussion