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

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

B - Practical Computing

やりたいこと

出力される文字列は以下のようなものをN行分、左寄せした形になる。

行	出力データ
1	1
2	1 1
3	1 2 1
4	1 3 3 1
5	1 4 6 4 1
…	…

入力値の取得

    // 入力値の取得
    val n = readLine()!!.toInt()

出力データを格納する配列の宣言

出力データはN行で、i行目(0スタート）の長さは i+1 となる。

    // 出力データを格納する配列を宣言
    val a = Array(n) { IntArray(it + 1) }

あとはこの配列に仕様通りのデータを格納していこう。

サンプルコード

main.kt

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

    // 出力データを格納する配列を宣言
    val a = Array(n) { IntArray(it + 1) }


    for (i in a.indices) {
        for (j in a[i].indices) {
            if (j == 0 || j == i) {
                a[i][j] = 1
            } else {
                a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
            }
        }
    }

    // 答えを出力
    a.forEach { it.joinToString(" ").let { println(it) } }
}

C - K Swap

やりたいこと

入力で与えられた数列を操作して、昇順にソートされた状態を目指す。操作は以下条件を満たす2つの要素の入れ替え。
条件：要素1と要素2の現在の位置（インデックス）の差がKの倍数であること。
昇順にソートすることが可能かどうかを判定したい。

1. 入力で与えられた配列を昇順にソートする。
2. ソートされた配列を用いて、数値がどの位置に収まるべきかをMap化する。
3. 各数値について、現在の位置と収まるべき位置の差がKの倍数になるかどうかをチェックする。

以上で昇順ソート状態にすることが可能かどうかを判定しよう。

入力値の取得

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

数値 - 収まるべき位置のMapを作成

数値から収まるべき位置を取得できるMapを作成しよう。入力で与えられる数列はユニークではないため、 同じ数値が複数存在する 可能性がある。そのためMapの型は Map<Int, Int>　では格納できない。また、実際に判定処理を行う場合の処理済みを管理するフラグも格納したいため Map<Int,SortedMap<Int,Boolean>>とした。

    // 数値 - 収まるべき位置のMapを作成する処理
    val dic = mutableMapOf<Int, SortedMap<Int, Boolean>>()
    for (i in sorted.indices) {
        val num = sorted[i]
        if (!dic.containsKey(num)) {
            dic[num] = sortedMapOf()
        }
        dic[num]!![i] = false
    }

判定処理

それぞれの数値に対して、収まるべき位置候補が存在するかどうかを確認しよう。同じ数値が存在しうるので、一度収まるべき位置候補となったものは使用済みとしてフラグを立てて重複利用を防止しよう。

    // 判定処理
    for (i in a.indices) {
        val num = a[i]
        var isMatch = false
        for (j in dic[num]!!) {
            // 収まるべき位置候補の中に 現在位置との差がkの倍数であるものを探す
            if ((!j.value) && j.key % k == i % k) {
                // マッチするものが見つかったら、同じ数値で再利用されぬようフラグを立てよう
                dic[num]!![j.key] = true
                isMatch = true
                break
            }
        }
        if (!isMatch) {
            // 収まるべき位置候補が見つからない数値が一つでもあれば昇順ソート化は不可
            return false
        }
    }

サンプルコード

main.kt

import java.util.SortedMap

fun main(args: Array<String>) {
    println(if (getAns()) "Yes" else "No")
}

fun getAns(): Boolean {
    // 入力値の取得
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }

    // 入力値で与えられた配列を昇順にソート
    val sorted = a.sorted()
    // 数値 - 収まるべき位置のMapを作成する処理
    val dic = mutableMapOf<Int, SortedMap<Int, Boolean>>()
    for (i in sorted.indices) {
        val num = sorted[i]
        if (!dic.containsKey(num)) {
            dic[num] = sortedMapOf()
        }
        dic[num]!![i] = false
    }

    // 判定処理
    for (i in a.indices) {
        val num = a[i]
        var isMatch = false
        for (j in dic[num]!!) {
            // 収まるべき位置候補の中に 現在位置との差がkの倍数であるものを探す
            if ((!j.value) && j.key % k == i % k) {
                // マッチするものが見つかったら、同じ数値で再利用されぬようフラグを立てよう
                dic[num]!![j.key] = true
                isMatch = true
                break
            }
        }
        if (!isMatch) {
            // 収まるべき位置候補が見つからない数値が一つでもあれば昇順ソート化は不可
            return false
        }
    }
    return true
}