AtCoder Beginner Contest 273 A～Cのメモ

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）の参加記です。

https://atcoder.jp/contests/abc273

A Recursive Function

問題文の通り再帰関数を実装すればOKです。Nが小さいので計算量は気にしなくていいです。
Aで計算量の考慮が必要だったらびっくりですが。

fun main() {
    val n = readLine()!!.toInt()
    println(f(n))
}

fun f(k: Int): Int {
    if(k == 0) {
        return 1
    }

    return k * f(k - 1)
}

B - Broken Rounding

沼りました…
WA祭りで逐一パッチをあてるように修正していったのでツギハギです。

しかもコーナーケースも踏んでる。

基本的な戦略としては、各桁を分解して配列として持って各桁をチェックし、4より大きければ次の桁の値を1増やすというだけです。
ただ、それだけだとうまくいかない場合の考慮をいちいち入れています。

提出コードに対してコメントを後から追加しています。

fun main() {
    val (x, k) = readLine()!!.split(" ").map { it.toLong() }

    // 配列で扱いやすいように逆順にする
    val xl = x.toString().map { it - '0' }.reversed().toMutableList()
    for(i in 0 until k.toInt()) {
        // 範囲外を参照しないためのチェック
        if(i >= xl.size) {
            break
        }

        // 切り上げする場合
        if(xl[i] > 4) {
            // 切り上げによって桁が増える場合
            if(i + 1 == xl.size) {
                xl.add(1)
            } else {
                xl[i+1]++
            }
        }
        xl[i] = 0
    }

    // 上記だけだと一桁が「10」になってしまうケースがあるのでその対処
    var i = 0
    while(i < xl.size) {
        if(xl[i] >= 10) {
            if(i == xl.size - 1) {
                xl.add(1)
            } else {
                xl[i+1]++
            }
            xl[i] = 0
            i = 0
        }
        i++
    }
    // 逆順になっているので戻す
    // 頭に0がつくケースがあるのでLongに変換する
    println(xl.reversed().joinToString("").toLong())
}

しかし、こんなの標準ライブラリでできるのでは？とコンテスト後に気づいてやり直してみました。

import java.math.BigDecimal
import java.math.RoundingMode

fun main() {
    val (x, k) = readLine()!!.split(" ").map { it.toLong() }
    val decimal = BigDecimal(x)

    var index = -1
    val ans = (0 until k).fold(decimal) { acc, _ ->
        val s = acc.setScale(index, RoundingMode.HALF_UP).toPlainString()
        index--
        BigDecimal(s)
    }
    println(ans)
}

そうだよね…

これなら5分くらいで一発ACでした。

C - (K+1)-th Largest Number

N回ループが回るのは間違いないので、Kの一つ一つに対して定数時間か対数時間くらいで答えを求められればいけるという感じで考えました。

各Aごとの答え（数列内にそのAより大きい数は何種類あるか）は固定なので、線形時間くらいで求めて連想配列に入れておけばよさそうです。
しかしそれだけだとダメで、Kごとの答えを求めるためにいちいちAを走査していたら二重ループになってしまい間に合いません。

とりあえず、最初ハードルであるAごとの答えの求め方を考えます。こういう数列はソートすると嬉しい場合と、そうでもない場合とがありますが、今回は嬉しい場合な気がしたのでそれを考えてみます。
それで、ソートすれば二分探索が使えるようになりますので、これを使えばAごとの答えを求められそうですね。求める必要があるのは大きい値の数ではなく「種類」ですので、重複を排除した配列で考えるといいです。二分探索で調査対象の値のソート済の場合の位置がわかるので、それより後ろにある要素の個数が欲しい値です。

で、この処理を実行するときに何種類なのか判明するわけですが、それの件数が求めたい値そのものじゃないかと気づいたので、「何種類なのか」をキー、その出現回数をバリューとした連想配列に記録することにしました。
Kに対する答えは重複もカウントしますので、この値を求めるためには重複排除していない配列で考える必要があります。
Aの数列の添字とKはたまたま？一致しますので、Kの列挙とAの数列要素の列挙を兼ねて処理しています。

あとは、再度Kを列挙して連想配列から値を取り出すだけです。（取り出せない場合は0を出力）
出力が大量になるかもしれないのでPrintWriterを使います。

import java.io.PrintWriter

fun main() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toInt() }

    val ad = aList.distinct().sorted()

    val aMap = mutableMapOf<Int, Int>()
    val kMap = mutableMapOf<Int, Int>()
    for(k in 0 until n) {
        val a = aList[k]

        val index = ad.binarySearch(a)
        val count = if(index < 0) {
            0
        } else {
            ad.size - 1 - index
        }
        aMap[a] = count

        increment(kMap, count)
    }

    val out = PrintWriter(System.out)
    for(k in 0 until n) {
        if(kMap.containsKey(k)) {
            out.println(kMap[k])
        } else {
            out.println(0)
        }
    }
    out.flush()
}

fun increment(map: MutableMap<Int, Int>, n: Int) {
    if(map.containsKey(n)) {
        map[n] = map[n]!! + 1
    } else {
        map[n] = 1
    }
}

aMapはいらないよね？
二分探索の結果が見つからないことなんてないからその分岐もいらないよね？？

感想

Bは悔しいですね。コンテスト中にBigDecimalを使う解法が思いついていればノーペナでかつ時間が残ってD問題にも挑戦できたかもしれません。
まあこれでBigDecimalで整数も四捨五入できるとわかったので次からは大丈夫です。

Cも後から見直すといらないコードがあったりして反省点は色々ありますが、コンテスト中にノーペナで解けたのが嬉しくてまあいいやってなってます。

やはりC問題が解けると嬉しいですね。今回は楽しかったです！