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

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

B - Takahashi's Failure

やりたいこと

$A_1$~$A_n$（食品とする）のうち、最大の値（最大うまさとする）を求める。
食品のうち、値が最大うまさと一致する要素のインデックスを求めうまい食品インデックスとする
配列Cの内、$B_1$~$B_k$に含まれる要素が一つでもあればYes、一つもなければNo。

入力値の取得

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

$B_1$~$B_k$取得時時にit.toInt() - 1としていますが、入力値の範囲が1~nであるのに対し、実際に照合する対象は配列aのインデックスであり、その範囲は0~(n-1)となるため、1を引いています。

最大うまさとうまい食品インデックスの抽出

    // 最大うまさの取得
    val max = a.max()!!
    // 最大うまさの要素（うまい食品インデックス）を抽出
    val oishi = a.indices.filter { a[it] == max }

サンプルコード

main.kt

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

    // 最大うまさの取得
    val max = a.max()!!
    // 最大うまさの要素（うまい食品インデックス）を抽出
    val oishi = a.indices.filter { a[it] == max }
    // うまい食品インデックスの内、Bに含まれるものが1つ以上あれば”Yes"、一つもなければ"No"
    println(if (oishi.any { it in b }) "Yes" else "No")
}

C - Slot Strategy

やりたいこと

各リールは0~9を並べ替えたものとなっている。0~9のそれぞれについて揃えるのに必要な時間を算出して、その内の最小値を答えとして出力しよう。

揃えるのに必要な時間を算出する方法

仮にリールが5つあり、以下のようになっているとする。
これを全て1で揃える場合を考えよう。

位置（インデックス）	0	1	2	3	4	5	6	7	8	9
リール1	0	1	2	3	4	5	6	7	8	9
リール2	0	2	1	3	4	5	6	7	8	9
リール3	2	1	3	4	5	6	7	8	9	0
リール4	2	3	1	4	5	6	7	8	9	0
リール5	3	1	2	5	6	7	8	9	0	4

各リールの1の位置（インデックス）は以下のようになる

	位置（インデックス）
リール1	1
リール2	2
リール3	1
リール4	2
リール5	1

これを位置（インデックス値）をkey、対応するリールの個数をvalueとするMapに入れると以下のようになる。

key	value
1	3
2	2

インデックス値に重複がなければ（valueが1であれば）、インデックス値の最大が必要な時間となる。ボタンを1回押すごとに止められるリールは1つのため、二つ目はインデックス値+10秒後、3つ目はインデックス値+20秒後にボタンを押すこととなる。各keyについて最後にボタンが押されるタイミングは $(value-1)*10+key$ となる。

キー	値	最後にボタンが押されるタイミング
1	3	$(3-1)*10+1 = 21$
2	2	$(2-1)*10+2 = 12$

その最大値が 全てを1で揃える場合に必要な時間の最小値 となる。同様に0,2,3~9で揃える場合 に必要な時間を求め、それらの中で 一番小さいもの が答えとなる。

入力値の取得

    // 入力値の取得
    val n = readLine()!!.toInt()
    // リールの状態
    val s = (1..n).map { readLine()!!.map { it.toString().toInt() } }

0~9についての処理

    (0..9).map { number ->
        // 0~9のそれぞれの数(number)で揃えた場合の処理
    }

numberで揃える場合に必要な時間の算出

        val indexCount = mutableMapOf<Int,Int>()
        //　位置をkeyとし、それに対応するリールの個数をvalueとするmapの作成
        for(i in s) {
            val idx = i.indexOf(number)
            indexCount[idx] = (indexCount[idx]?:0)+1
        }
        // number で揃える場合に限必要な時間を求める
        indexCount.map { (it.value-1)*10 + it.key }.max()!!

サンプルコード

main.kt

fun main(args: Array<String>) {
    // 入力値の取得
    val n = readLine()!!.toInt()
    // リールの状態
    val s = (1..n).map { readLine()!!.map { it.toString().toInt() } }

    val ans = (0..9).map { number ->
        // 0~9のそれぞれの数(number)で揃えた場合の処理
        val indexCount = mutableMapOf<Int,Int>()
        //　位置をkeyとし、それに対応するリールの個数をvalueとするmapの作成
        for(i in s) {
            val idx = i.indexOf(number)
            indexCount[idx] = (indexCount[idx]?:0)+1
        }
        // number で揃える場合に限必要な時間を求める
        indexCount.map { (it.value-1)*10 + it.key }.max()!!
    }.min()
    println(ans)
}