😺

ABC277 C - Ladder Takahashiのメモ

2022/12/21に公開

AtCoder

競プロ

グラフ

tech

目についたC問題を解こうとしたところ解けなかった回です。

考察と解答

典型的なグラフの問題です。階が頂点ではしごが辺のグラフととらえてDFSなりBFSなりで探索して答えを求めます。入力された階が到達可能とは限らないので、単純に入力の最大値を答えとするのではなくちゃんと探索する必要があります。

この手のC問題にしては制約がきつく、注意しないとTLEになります。（なってました）

import kotlin.math.max

@OptIn(ExperimentalStdlibApi::class)
fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine()!!.toInt()

    val graph = mutableMapOf<Int, MutableList<Int>>()

    repeat(n) {
        val (a, b) = br.readLine()!!.split(" ").map { it.toInt() }
        graph.putIfAbsent(a, mutableListOf())
        graph[a]?.add(b)

        graph.putIfAbsent(b, mutableListOf())
        graph[b]?.add(a)
    }

    val stack = ArrayDeque<Int>()
    stack.add(1)

    val visited = mutableSetOf<Int>()
    visited.add(1)

    while (stack.isNotEmpty()) {
        val start = stack.removeLast()

        if(!graph.containsKey(start)) {
            continue
        }

        for(node in graph[start]!!) {
            if(visited.contains(node)) {
                continue
            }

            visited.add(node)
            stack.add(node)
        }
    }

    println(visited.max())
}

制約が大きいので二次元配列だとメモリが足りません。Mapを使うのがよいです。

あとは到達した階は探索済としてマークし、再度探索しないようにします。最初は移動元と移動先のペアで考えていたのですがその必要はなく、単純に移動先の階を探索済にしてしまってよいです。というより、そうしないと無駄な探索が発生してTLEになります。

あとは、初期位置が1階なので1階は固定で探索済にします。これを忘れてTLE祭りでした。結局自力で気づけず、教えてもらったという。悔しいですね。

振り返ってみるとわりとシンプルな問題なのですが、制約がキツイので少しのガバが命取りになる感があります。

なお、今回は非再帰DFSで解いています。再帰DFSでも通ったのですが、実行時間がギリギリになりました。

import kotlin.math.max

var graph = mutableMapOf(0 to mutableListOf(0))

fun main() {
    Thread(
        null,
        {
            val br = System.`in`.bufferedReader()
            val n = br.readLine()!!.toInt()

            graph = mutableMapOf()

            repeat(n) {
                val (a, b) = br.readLine()!!.split(" ").map { it.toInt() }
                graph.putIfAbsent(a, mutableListOf())
                graph[a]?.add(b)

                graph.putIfAbsent(b, mutableListOf())
                graph[b]?.add(a)
            }

            visited.add(1)

            dfs(1)
            println(ans)
        },
        "",
        128 * 1024 * 1024
    ).start()
}

var ans = 1

val visited = mutableSetOf<Int>()

fun dfs(start: Int) {
    if(!graph.containsKey(start)) {
        return
    }

    for(node in graph[start]!!) {
        if(visited.contains(node)) {
            continue
        }

        visited.add(start)

        ans = max(ans, node)
        dfs(node)
    }
}

まあ自分の実装にも何か問題はあるのでしょうけど、それにしても実はKotlinって再帰は苦手なんじゃないかなあという印象を持ってしまいました。

感想

グラフ難しいです。練習不足ですね。

考察と解答

感想

Discussion