AtCoder B,C問題をKotlinで解こう - ABC270

当記事ではAtCoder、ABCのB問題ならびにC問題（時々D問題も）のKotlinでの解法を超初心者向けに詳細に解説します。

同記事をZennにも投稿しています。

B - Hammer

やりたいこと

スタート、ゴール、壁、ハンマーの位置関係で場合分けを行い、スタートからゴールまでの最短移動距離を求めよう。ゴールに到達できない場合は-1を出力しよう。

位置関係の場合わけは以下の3パターンとなる。

1. スタートとゴールの間に壁がある場合
   1. スタートとハンマーの間に壁がある場合
      ゴールに到達できない
   2. スタートとハンマーの間に壁がない場合
      スタートからハンマーまで移動し、ハンマーからゴールに移動する
2. スタートとゴールの間に壁がない場合
   スタートからゴールに移動する。

入力値の取得

    // 入力値の取得
    val (x, y, z) = readln().split(" ").map { it.toInt() }

サンプルコード

main.kt

fun main(args: Array<String>) {
    println(getAns())
}

fun getAns(): Int {
    // 入力値の取得
    val (x, y, z) = readln().split(" ").map { it.toInt() }

    // スタート、ゴール、壁、ハンマーの位置関係で場合分けをする
    return if (y in 0..x || y in x..0) {
        // スタートからゴールまでの間に壁がある
        if (y in 0..z || y in z..0) {
            // スタートからハンマーまでの間に壁がある
            // この場合ゴール不可能
            -1
        } else {
            // スタートからハンマーまでの間に壁はない
            // ハンマーを拾ってからゴールを目指す
            Math.abs(z) + Math.abs(x - z)
        }
    } else {
        // スタートからゴールまでの間に壁はないのでそのままゴールできる
        Math.abs(x)
    }
}

C - Simple path

やりたいこと

• x から y への最短経路を求める。
  • 最短距離を求め、経路の復元を行う。

幅優先探索 を行い、x から 各頂点への最短距離を求める。各頂点への最短距離を求める際に、どこの頂点から来たのか を保持して、経路の復元を行えるようにする。

入力値の取得

    // 入力値の取得
    val (n,x,y) = readln().split(" ").map { it.toInt() }
    // 頂点同士の繋がりを取得
    val connect = Array(n+1) { mutableSetOf<Int>() }
    repeat(n-1) {
        val (a,b) = readln().split(" ").map { it.toInt() }
        connect[a].add(b)
        connect[b].add(a)
    }

サンプルコード

main.kt

import java.util.LinkedList

fun main(args: Array<String>) {
    // 入力値の取得
    val (n, x, y) = readln().split(" ").map { it.toInt() }
    // 頂点同士の繋がりを取得
    val connect = Array(n + 1) { mutableSetOf<Int>() }
    repeat(n - 1) {
        val (a, b) = readln().split(" ").map { it.toInt() }
        connect[a].add(b)
        connect[b].add(a)
    }

    // x からの距離を保持
    val step = IntArray(n + 1) { Int.MAX_VALUE }
    // どこの頂点から移動してきたのかを保持
    val from = IntArray(n + 1)

    // x -> y へ移動する場合の最短距離とその経路を求める
    val queue = LinkedList<Int>()
    queue.add(x)
    step[x] = 0
    
    // 幅優先探索を行う
    while (queue.isNotEmpty()) {
        val cur = queue.pop()
        if (cur == y) {
            // y はゴールなので、それ以上は処理しなくていい
            break
        }
        for (i in connect[cur]) {
            if (step[i] <= step[cur] + 1) {
                continue
            }
            step[i] = step[cur] + 1
            from[i] = cur
            queue.add(i)
        }
    }

    // y から移動元を辿って経路を復元
    val route = mutableListOf(y)
    while (route.last() != x) {
        route.add(from[route.last()])
    }
    println(route.reversed().joinToString(" "))
}