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

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

B - Batters

やりたいこと

要素数4の整数配列を用意する。
入力された数列Aの要素毎に以下の処理を行う。

• 配列の先頭要素を+1する。
• 配列の各要素の値をAの要素の値分後ろに移動する。

入力値の取得

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

数列Aの要素毎の処理

    // 処理用の要素数4の整数配列
    var box = IntArray(4)

    // 答えを格納するための変数
    var p = 0

    // 数列Aの要素毎の処理
    for (i in a) {
        box[0] = 1
        // 配列の要素末尾から処理を行う
        for (j in box.indices.reversed()) {
            val next = j + i
            if (next > box.lastIndex) {
                p += box[j]
            } else {
                box[next] += box[j]
            }
            box[j] = 0
        }
    }

配列の要素末尾から処理を行うのは要素の衝突を避けるためです。

サンプルコード

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

    // 処理用の要素数4の整数配列
    var box = IntArray(4)

    // 答えを格納するための変数
    var p = 0

    // 数列Aの要素毎の処理
    for (i in a) {
        box[0] = 1
        // 配列の要素末尾から処理を行う
        for (j in box.indices.reversed()) {
            val next = j + i
            if (next > box.lastIndex) {
                p += box[j]
            } else {
                box[next] += box[j]
            }
            box[j] = 0
        }
    }
    println(p)
}

C - Filling 3x3 array

やりたいこと

3*3の2次元配列があると想定して、各行ごとの合計値と各列ごとの合計値が入力値として与えられます。それぞれの合計値に矛盾がないように2次元配列に 正整数 を配置した場合に、その組み合わせが何通りになるのかを数えたい。

入力値の取得

    // 入力値の取得
    val inpt = readLine()!!.split(" ").map { it.toInt() }
    // h1~h3
    val h = inpt.take(3)
    // w1~w3
    val w = inpt.drop(3)

全ての組み合わせの試行

各行、列毎に2つの要素が決定すれば残り1つも決定できる。
つまり左上の4要素が決定すれば2次元配列の全体を決定することができる。

入力値によって2次元配列の各要素の上限は決まる。入力の上限は30。その範囲で左上の4要素の組み合わせは $30^4 = 81*10^4$ となり、決して多くはない。

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val inpt = readLine()!!.split(" ").map { it.toInt() }
    // h1~h3
    val h = inpt.take(3)
    // w1~w3
    val w = inpt.drop(3)

    // 答えを計上するための変数
    var ans = 0

    // 1行目1列目の要素が決定
    for (r1c1 in 1..30) {
        // 1行目2列目の要素が決定
        for (r1c2 in 1..30) {
            // 1行めの1~2列目の要素が決定したので、3列目の要素も決定できる
            val r1c3 = h[0] - r1c1 - r1c2
            if (r1c3 <= 0) {
                // 条件は正の整数である場合なので、そうならない場合は計上しない
                break
            }
            // 2行目1列目の要素が決定
            for (r2c1 in 1..30) {
                // 2行目2列目の要素が決定
                for (r2c2 in (1..30)) {
                    // 2行目1~2列目の要素が決定したので3列目の要素も決定できる
                    val r2c3 = h[1] - r2c1 - r2c2
                    if (r2c3 <= 0) {
                        // 条件は正の整数である場合なので、そうならない場合は計上しない
                        break
                    }
                    // 1~2行目の要素が決定したため、3行目の各要素も決定できる
                    val r3 = IntArray(3)
                    r3[0] = w[0] - r1c1 - r2c1
                    r3[1] = w[1] - r1c2 - r2c2
                    r3[2] = w[2] - r1c3 - r2c3
                    if (r3.any { it <= 0 }) {
                        // 条件は正の整数である場合なので、そうならない場合は計上しない
                        continue
                    }
                    if (r3.sum() != h[2]) {
                        // 3行目の各要素の合計値がh3と一致しない場合は計上しない
                        continue
                    }
                    ans++
                }
            }
        }
    }
    println(ans)
}