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

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

B - At Most 3 (Judge ver.)

やりたいこと

3重のループを回して、あり得る合計数をセットに保持する。最終的にセットの要素数を出力しよう。
不要なループをスキップさせるため、おもりはあらかじめ昇順でソートしよう。

入力値の取得

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

3重のループ処理

    // 良い整数を格納するセット
    val total = mutableSetOf<Int>()
    for (i in a.indices) {
        if (a[i] > w) {
            // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
            break
        }
        // おもりを1個だけ選択した場合
        total.add(a[i])
        // おもりを2個以上選択した場合
        for (j in (i + 1..a.lastIndex)) {
            if (a[i] + a[j] > w) {
                // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
                break
            }
            // おもりを2個選択した場合
            total.add(a[i] + a[j])
            // おもりを3個以上選択した場合
            for (k in (j + 1..a.lastIndex)) {
                if (a[i] + a[j] + a[k] > w) {
                    // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
                    break
                }
                // おもりを3個選択した場合
                total.add(a[i] + a[j] + a[k])
            }
        }
    }

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val (n, w) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
    // 良い整数を格納するセット
    val total = mutableSetOf<Int>()
    for (i in a.indices) {
        if (a[i] > w) {
            // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
            break
        }
        // おもりを1個だけ選択した場合
        total.add(a[i])
        // おもりを2個以上選択した場合
        for (j in (i + 1..a.lastIndex)) {
            if (a[i] + a[j] > w) {
                // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
                break
            }
            // おもりを2個選択した場合
            total.add(a[i] + a[j])
            // おもりを3個以上選択した場合
            for (k in (j + 1..a.lastIndex)) {
                if (a[i] + a[j] + a[k] > w) {
                    // 昇順にソートされているため、以降は全てwの値を超えるため、良い整数とならない
                    break
                }
                // おもりを3個選択した場合
                total.add(a[i] + a[j] + a[k])
            }
        }
    }
    println(total.size)
}

C - Poem Online Judge

やりたいこと

N回入力されるポエムである文字列とスコアとなる整数と入力順を保持する。
同じポエムが複数回入力されることがあるが、その場合後から入力されたものは無視する。全ての入力が終わった後、保持されているポエムとスコアのうち、最もスコアが大きいポエムの入力順を選ぶ。最も大きいスコアのポエムが複数ある時は、入力順が最も小さいものを選ぶ。

入力値の取得

入力されるポエムをキーとしてMapにスコアと入力順を保持しよう。

    // 入力値の取得
    val n = readLine()!!.toInt()
    // ポエム（文字列）をキーとしたスコアを保持するmap
    val score = mutableMapOf<String, Int>()
    // ポエム（文字列）をキーとした入力順を保持するmap
    val index = mutableMapOf<String, Int>()

    for (i in 1..n) {
        val (s, t) = readLine()!!.split(" ")
        if (score.containsKey(s)) {
            // scoreに既に値が存在しているので、オリジナルではない
            continue
        }
        // スコアの保持
        score[s] = t.toInt()
        // 入力順の保持
        index[s] = i
    }

最高得点ポエムの入力順を取得

スコアを保持するmapから得点の最大値を取得しよう。
その後同mapから得点の最大値と一致する値を持つ要素のキーを取得しよう。

    // 最高得点を取得
    val maxScore = score.values.max()!!
    // 最高得点のポエムを取得
    val maxScorePoem = score.filter { it.value == maxScore }.keys
    // 最高得点のポエムの入力順のうち最小のものを答えとする
    val ans = maxScorePoem.map { index[it]!! }.min()!!

サンプルコード

fun main(args: Array<String>) {
    // 入力値の取得
    val n = readLine()!!.toInt()
    // ポエム（文字列）をキーとしたスコアを保持するmap
    val score = mutableMapOf<String, Int>()
    // ポエム（文字列）をキーとした入力順を保持するmap
    val index = mutableMapOf<String, Int>()

    for (i in 1..n) {
        val (s, t) = readLine()!!.split(" ")
        if (score.containsKey(s)) {
            // scoreに既に値が存在しているので、オリジナルではない
            continue
        }
        // スコアの保持
        score[s] = t.toInt()
        // 入力順の保持
        index[s] = i
    }

    // 最高得点を取得
    val maxScore = score.values.max()!!
    // 最高得点のポエムを取得
    val maxScorePoem = score.filter { it.value == maxScore }.keys
    // 最高得点のポエムの入力順のうち最小のものを答えとする
    val ans = maxScorePoem.map { index[it]!! }.min()!!
    println(ans)
}