🐙

ABC285D - Change Usernamesのメモ

2023/01/19に公開

AtCoder

競プロ

グラフ

tech

前回のコンテストで解けなかったので解説ACです。

解説にコードが載っていないので、コード自体は自分で考えたものになります。

考察

考察といっても解説を見ているので、解説をもとに考えるだけですが、一応基本的な考え方についてはおさらいしておきます。
ユーザ名変更をするとき、変更後のユーザ名が存在しなければ実行できますが、存在する場合はその時点では実行できません。しかし、変更後の名前と同じ名前のユーザが他の名前に変更するのであれば実行できることになります。なので、それを考慮した上で全てのユーザ名変更が実行できるのか判定する問題です。
とコンテスト中にはそのように考えていたのですが、よく考えたらユーザ名の変更は全員が実行しようとしているんですね。
なので「変更後の名前と同じ名前のユーザが他の名前に変更するのであれば」ではなく、変更するのは確実だけど、その変更は成功するのかという話でした。ささいな違いなようでいて、この認識のずれが致命的だったと思います…

グラフかもってコンテスト中にも考えましたが、無向グラフでやろうとしてました。実際には $Si$ から $Ti$ への有向グラフでいいようでした。
ユーザ名を変更しようとしてないユーザはいないので、変更後の名前が既に存在するのであれば変更後の名前から伸びる辺についての情報も必ず入力されるので、単純に $Si$ から $Ti$ への有向グラフにすれば必要な探索は実行できます。コンテスト中にはそれにも気づきませんでした。
（だから無向グラフで考えたっていうのは今思えば意味不明なんですが…）

それで、グラフを辿ってサイクルが検出されたら答えはNo、サイクルがなければYesとなります。
サイクルがある状態とは、「AはBに変更しようとしている、BはCに変更しようとしている、CはAに変更しようとしている、Aは…」みたいに誰の変更も実行できない状態ですね。
こう書くとすごく当たり前な気がしますね。ズバリ「サイクルが存在することを判定」と言われないと気づかないとは、すごく、まだまだという感じがします。

「出次数が 0 である頂点へ向かう辺に対応するユーザ名の変更を行い、その頂点を削除する」

出次数はその頂点から伸びる辺の数ですね。それが0であれば、そのユーザ名変更は実行してよく、ユーザ名の変更とは実装上はグラフからその頂点を削除することで表現すると。

出次数が0ということは、その部分については明らかにサイクルは存在しないので変更が実行できると。
なお、サイクルがなければ変更を実行できるというのは、 $T_1,...,T_N$ は相異なるという制約によります。変更後の名前に変更しようとしているユーザが他にはいないことがわかっているので成り立ちます。
変更が実行できる場合に、変更前の名前の頂点を削除していいのも同じ理由です。その名前に変更しようとしているユーザは他にはいないからです。

この制約により、いずれの頂点も入次数、出次数ともに0か1というシンプルなグラフになりますね。

この辺りまでわかれば実装できそうです。

実装

最初に試行した実装が以下です。

頂点が文字列のグラフなのでMapで表現します。次数が2以上にならないので、Mapの値は配列ではなく単一の文字列です。

キューを使ってBFS風に実装しています。まあ次数が0か1なので、あくまでもBFS風です。

グラフは連結とは全然限らないので、 $Si$ は全て試す必要があります。
サイクル検出のために探索済の頂点を保持するSetが seen です。これは $Si$ それぞれで独立して管理します。seenに値があったら同じ頂点を再度訪問したということなのでサイクルです。

頂点から伸びる辺があればそこに進み、なければその頂点へ頂点を伸ばしている元の辺を削除します。

fun main() {
    val n = readLine()!!.toInt()

    val graph = mutableMapOf<String, String>()

    val sList = mutableListOf<String>()

    repeat(n) {
        val (s, t) = readLine()!!.split(" ")

        graph[s] = t
        sList.add(s)
    }

    val queue = java.util.ArrayDeque<String>()
    for(s in sList) {
        queue.add(s)

        val seen = mutableSetOf<String>()
        var prev = ""
        while (queue.isNotEmpty()) {
            val v = queue.poll()

            if(v in seen) {
                println("No")
                return
            }

            seen.add(v)

            if(v in graph) {
                queue.add(graph[v]!!)
                prev = v
            } else {
                graph.remove(prev)
                break
            }
        }
    }
    println("Yes")
}

しかし、これだと二重ループなのでダメそうな気がしました。

はい、これは想像通りでした。

これだと探索済の頂点のうち最後の部分しか削除していないので、無駄な探索が発生します。

もうちょっと考えてみて、既に探索した頂点を再度探索することはないと気づきました。同じ名前に変更しようとするユーザが複数いることはないので。ということは、探索済の頂点はもうその時点で削除していいことになります。それで無駄な探索を防げます。

fun main() {
    val n = readLine()!!.toInt()

    val graph = mutableMapOf<String, String>()

    val sList = mutableListOf<String>()

    repeat(n) {
        val (s, t) = readLine()!!.split(" ")

        graph[s] = t
        sList.add(s)
    }

    val queue = java.util.ArrayDeque<String>()
    for(s in sList) {
        queue.add(s)

        val seen = mutableSetOf<String>()
        while (queue.isNotEmpty()) {
            val v = queue.poll()

            if(v in seen) {
                println("No")
                return
            }

            seen.add(v)

            if(v in graph) {
                queue.add(graph[v]!!)
                graph.remove(v)
            }
        }
    }
    println("Yes")
}

これでOKでした。

感想

グラフの練習が全然足りない。

（執筆時間：54分58秒）

考察

実装

感想

Discussion