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

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

B - 1D Pawn

やりたいこと

1回のクエリに対してコマの動きは

• コマが右端にあるときは移動しない
• コマの右マスにコマがある時は移動しない
• 上2件のどちらにも当てはまらない場合右に1マス移動

となっている。
つまり コマの順序は入れ替わらない。左からx個目のコマは何度操作が行われても左からx個目のコマであり続ける。
各コマが現在どの位置にいるのかを配列で管理しよう。

入力値の取得

    val (n, k, q) = readLine()!!.split(" ").map { it.toInt() }

    // 各コマの位置。入力値は最初からソートされているので、そのままコマの位置を保持する配列にしよう。
    val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    // 操作
    // 左からx個目の情報を配列のインデックスとするため、−1 している
    val l = readLine()!!.split(" ").map { it.toInt() - 1 }

各コマに対する操作

各コマに対する操作を実装しよう。

    for (i in l) {
        // 実際に操作を行う
        if (a[i] == n) {
            // コマが右端にある場合
            continue
        }
        if (i < a.lastIndex && a[i] + 1 == a[i + 1]) {
            // コマの右隣に別のコマがある場合
            continue
        }
        // コマを1マス右に移動
        a[i]++
    }

サンプルコード

main.kt

fun main(args: Array<String>) {
    val (n, k, q) = readLine()!!.split(" ").map { it.toInt() }

    // 各コマの位置。入力値は最初からソートされているので、そのままコマの位置を保持する配列にしよう。
    val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    // 操作
    // 左からx個目の情報を配列のインデックスとするため、−1 している
    val l = readLine()!!.split(" ").map { it.toInt() - 1 }

    for (i in l) {
        // 実際に操作を行う
        if (a[i] == n) {
            // コマが右端にある場合
            continue
        }
        if (i < a.lastIndex && a[i] + 1 == a[i + 1]) {
            // コマの右隣に別のコマがある場合
            continue
        }
        // コマを1マス右に移動
        a[i]++
    }
    // 答えの出力
    println(a.joinToString(" "))
}

C - Robot Takahashi

やりたいこと

ある体重を大人と子供の境界と設定する。その体重以上の大人とその体重未満の子供の数を最大化できる境界が答えとなる。
入力された体重を「大人」と「子供」に分けて降順にソートし、キューに格納しよう。子供のキューを順に大人と子供の境界値として処理し、それぞれの境界値ごとに 正しくカウントされた子供 + (大人の総数 - 正しくカウントされなかった大人） を算出し、その最大値を求めよう。

入力値の取得

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

データを大人と子供に分ける

体重データを大人と子供に分けて、それぞれ降順にソートしよう。

    // 大人と子供に分ける
    val a = (0 until n).filter { s[it] == '1' }.map { w[it] }.sortedDescending()
    val c = (0 until n).filter { s[it] != '1' }.map { w[it] }.sortedDescending()

    // 正しくカウントされなかった大人
    val aRemovedQueue = LinkedList(a)

    // 正しくカウントされた子供
    val cQueue = LinkedList(c)

キューの処理

正しくカウントされた子供のキューごとに処理を行う。子供のキューの先頭と大人のキューの先頭を比較し、大人のキューが大きい場合は削除しよう。そうすると子供のキューの先頭を大人と子供の境界とした場合の「正しくカウントされた子供」「正しくカウントされなかった大人」の状態となる。正しくカウントされた子供＋（大人の総数 - 正しくカウントされなかった大人）の最大値を探そう。

    var ans = Math.max(a.size, c.size)
    while (aRemovedQueue.isNotEmpty() && cQueue.isNotEmpty()) {
        // 正しくカウントされた子供の最大値を子供と大人の境界の体重とする
        // 正しくカウントされた子供の最大値以上の体重である「正しくカウントされた大人」を正しくカウントされなかったキューから削除する
        while (aRemovedQueue.isNotEmpty() && cQueue.peek() < aRemovedQueue.peek()) {
            aRemovedQueue.pop()
        }
        ans = Math.max(cQueue.size + (a.size - aRemovedQueue.size), ans)
        if (cQueue.isNotEmpty()) {
            cQueue.pop()
        }
    }

サンプルコード

main.kt

import java.util.LinkedList

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

    // 大人と子供に分ける
    val a = (0 until n).filter { s[it] == '1' }.map { w[it] }.sortedDescending()
    val c = (0 until n).filter { s[it] != '1' }.map { w[it] }.sortedDescending()

    // 正しくカウントされなかった大人
    val aRemovedQueue = LinkedList(a)

    // 正しくカウントされた子供
    val cQueue = LinkedList(c)

    var ans = Math.max(a.size, c.size)
    while (aRemovedQueue.isNotEmpty() && cQueue.isNotEmpty()) {
        // 正しくカウントされた子供の最大値を子供と大人の境界の体重とする
        // 正しくカウントされた子供の最大値以上の体重である「正しくカウントされた大人」を正しくカウントされなかったキューから削除する
        while (aRemovedQueue.isNotEmpty() && cQueue.peek() < aRemovedQueue.peek()) {
            aRemovedQueue.pop()
        }
        ans = Math.max(cQueue.size + (a.size - aRemovedQueue.size), ans)
        if (cQueue.isNotEmpty()) {
            cQueue.pop()
        }
    }
    println(ans)
}