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

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

B - Triangle (Easier)

やりたいこと

頂点の数は最大で100と多くはない。A<B<Cが成立する全ての頂点の組み合わせに対して

• A,B間に辺が存在する
• B,C間に辺が存在する
• A,C間に辺が存在する

以上の3条件を満たすかどうかをチェックし、計上していこう。

入力値の取得

辺の情報は、辺が結ぶ2点をインデックスとして使用するBool型の2次元配列を作って管理しよう。

    // 入力値の取得
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    // 辺の情報を保持する配列
    val path = Array(n + 1) { BooleanArray(n + 1) }
    // 辺の情報の取得
    (1..m).map {
        val (u, v) = readLine()!!.split(" ").map { it.toInt() }
        path[u][v] = true
    }

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    // 辺の情報を保持する配列
    val path = Array(n + 1) { BooleanArray(n + 1) }
    // 辺の情報の取得
    (1..m).map {
        val (u, v) = readLine()!!.split(" ").map { it.toInt() }
        path[u][v] = true
    }

    var ans = 0
    for (a in (1..n - 2)) {
        for (b in (a + 1..n - 1)) {
            if (!path[a][b]) {
                // 頂点(a,b)間に辺が無い場合
                continue
            }
            // a,b,c間それぞれに辺のあるものを計上する
            ans += (b + 1..n).count { c -> path[b][c] && path[a][c] }
        }
    }
    println(ans)
}

C - Min Max Pair

やりたいこと

条件を満たすペアは以下の２パターンとなる。

• 共に要素の値と要素のインデックス値が一致している。
• 要素の値と要素のインデックス値が入れ替わっている。

前者は値とインデックス値が一致している要素の数を仮にmとすれば $m*(m-1)/2$ で求められる。
後者は入力で与えられた要素を順に処理し、現在処理中の要素(a1)の値のインデックス値の要素（a2)の値がa1のインデックス値と一致しているかどうかを判定すれば良い。

入力値の取得

    // 入力値の取得
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() - 1 }

条件を満たすペアの計上

数列aを順に処理していき、後者のケースで$(a_i,a_j)$のペアが条件を満たすときiを処理している時とjを処理している時で二重に計上されないよう対策しよう。

    var ans = 0L
    for (i in a.indices) {
        if (i == a[i]) {
            // 要素のインデックス値と値が一致している場合
            indexAndValueMatch++
        } else if (a[i] > i) {
            // 二重に形状されることを防ぐため、要素の値がインデックス値よりも大きいものに限定して処理する。
            if (a[a[i]] == i) {
                // 要素(a1)の値をインデックス値としてもつ要素(a2)の値がa1のインデックス値と一致しているかを判定
                ans++
            }
        }
    }
    ans += indexAndValueMatch.let { it.toLong() * (it - 1) / 2 }

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() - 1 }

    // 要素のインデックスと値が一致しているものの数
    var indexAndValueMatch = 0

    var ans = 0L
    for (i in a.indices) {
        if (i == a[i]) {
            // 要素のインデックス値と値が一致している場合
            indexAndValueMatch++
        } else if (a[i] > i) {
            // 二重に形状されることを防ぐため、要素の値がインデックス値よりも大きいものに限定して処理する。
            if (a[a[i]] == i) {
                // 要素(a1)の値をインデックス値としてもつ要素(a2)の値がa1のインデックス値と一致しているかを判定
                ans++
            }
        }
    }
    ans += indexAndValueMatch.let { it.toLong() * (it - 1) / 2 }
    println(ans)
}