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

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

B - Better Students Are Needed!

やりたいこと

受験生を3種類のソート条件でソートし、上位から(x,y,z)人を取り出してSetに格納しよう。
同じ受験生を重複して合格者としないよう気をつけよう。

入力値の取得

    // 入力値の取得
    val (n, x, y, z) = readLine()!!.split(" ").map { it.toInt() }
    // 数学のスコア
    val a = readLine()!!.split(" ").map { it.toInt() }
    // 英語のスコア
    val b = readLine()!!.split(" ").map { it.toInt() }

Comparator の作成

合格基準となるスコアの配列を渡して、渡されたスコアによってソートできるようComparatorを作成しよう。

class Comp(private val target: List<Int>) : Comparator<Int> {
    override fun compare(o1: Int?, o2: Int?): Int {
        if (target[o1!!] == target[o2!!]) {
            return o1!!.compareTo(o2!!)
        }
        return target[o1!!].compareTo(target[o2!!]) * -1
    }
}

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val (n, x, y, z) = readLine()!!.split(" ").map { it.toInt() }
    // 数学のスコア
    val a = readLine()!!.split(" ").map { it.toInt() }
    // 英語のスコア
    val b = readLine()!!.split(" ").map { it.toInt() }

    // 合格済みの受験生
    val passed = mutableSetOf<Int>()
    passed.addAll((0 until n).sortedWith(Comp(a)).take(x))
    passed.addAll((0 until n).filter { it !in passed }.sortedWith(Comp(b)).take(y))
    passed.addAll((0 until n).filter { it !in passed }.sortedWith(Comp(a.indices.map { a[it] + b[it] })).take(z))
    passed.sorted().map { it + 1 }.forEach { println(it) }
}

class Comp(private val target: List<Int>) : Comparator<Int> {
    override fun compare(o1: Int?, o2: Int?): Int {
        if (target[o1!!] == target[o2!!]) {
            return o1!!.compareTo(o2!!)
        }
        return target[o1!!].compareTo(target[o2!!]) * -1
    }
}

C - Changing Jewels

やりたいこと

レベルの最大値は10と少ない。順番に処理していこう

• レベルNの赤い宝石を変換（レベルNの青い宝石の数が確定する）
• レベルNの青い宝石を変換（レベルN-1の赤い宝石の数が確定する）
• レベルN-1の赤い宝石を変換（レベルN-1の青い宝石の数が確定する）
• レベルN-1の青い宝石を変換（レベルN-2の赤い宝石の数が確定する）
• レベルN-2の赤い宝石を変換（レベルN-2の青い宝石の数が確定する）
  ：

という順でレベル1まで処理していこう

入力値の取得

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

サンプルコード

main.kt

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

    // 赤い宝石の数を格納する配列
    val red = LongArray(n + 1)
    // 青い宝石の数を格納する配列
    val blue = LongArray(n + 1)

    // 最初はレベルnの赤い宝石が1個
    red[n] = 1
    for (i in (n downTo 2)) {
        // 赤い宝石の変換処理
        red[i - 1] += red[i]
        blue[i] += red[i] * x

        // 青い宝石の変換処理
        red[i - 1] += blue[i]
        blue[i - 1] += blue[i] * y
    }
    println(blue[1])
}