👋

AtCoder Beginner Contest 290 A~Cのメモ

2023/02/20に公開

Toyota Programming Contest 2023 Spring Qual B(AtCoder Beginner Contest 290)に参加したので記録を残します。
https://atcoder.jp/contests/abc290

今回は2ペナ3完で微冷えです。

A - Contest Result

AiBi番目の合計値を計算すればいいです。1-indexedなので補正します。

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    val b = readLine()!!.split(" ").map { it.toInt() }

    var sum = 0
    for(i in b.indices) {
        sum += a[b[i] - 1]
    }
    println(sum)
}

B - Qual B

基本は希望するかどうかをそのまま出力する、しかしK人以下にするための条件を入れます。

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

    var cnt = 0
    for(i in 0 until n) {
        if(s[i] == 'o' && cnt < k) {
            print('o')
            cnt++
        } else {
            print('x')
        }
    }
    println()
}

いちいちリテラルを書いているのは微妙な気がする…

C - Max MEX

2ペナもらったのはここです…

愚直解だと間に合わないです。
MEXとしてあり得るためには0からの連番になっている必要があります。0から欠けることなくm未満の数が揃っている必要があるのと、K個しか抜き出せないので答えは最大でもKであるというのがわかります。
なのでK以上の数はいらないです。K未満の数だけ抽出して考えます。連続部分列でなくてもいいので、いらない数は単純に無視するだけで問題ないです。

K未満の数だけ抽出したら、あとは0からカウントして途切れずに到達できた数より1大きい数が答えです。
順不同なので、昇順ソートして0から数えるようにします。そのままだと重複要素が邪魔なので除外します。K以上の数を無視したのと同じで、任意の数を抽出できるので重複は単に除外すればいいです。

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

    var list = mutableListOf<Int>()

    for(a in aList) {
        if(a < k) {
            list.add(a)
        }
    }
    list = list.distinct().sorted().toMutableList()

    var ans = 0
    for(i in list) {
        if(i == ans) {
            ans++
        } else {
            break
        }
    }
    println(ans)
}

filterを使わずにMutableListを作ってfor文を回すとかしているあたり、かなり混乱してそうです…
最後のbreakは競プロ的にはいらないですね。

D - Marking

一応見たけど、10^9という制約が見えるので、いかにも計算で求めそうだとはわかりました。テストケースが複数入力されるけど、O(N)とかだと1テストケースだけだとしてもTLEになりそうなくらい厳しい。
そんな数学要素が強そうな問題が私に解けるわけないじゃないですかーってことで早々に諦めました。

感想

2ペナは痛いですが、実のところABでも若干もたついたくらいコンディションは悪かったので、2ペナで済んでよかったねーという印象…(なんか異様に眠かった)
今回は仕方ないです。

Dがわからなかったのも今回はしょうがないですが、ずっとこのノリだと待っているのは停滞 or 衰退なので、数学も頑張らないとなあという感じ。
一応やっていますが、あとちょっとで中学数学の範囲は終わる、というくらいです。現時点だとさすがにまだ恩恵を感じないです。中学レベルだとまだチュートリアルなんだろうなという気がします。

いろいろ思うところがあるものの、チュートリアルがまだ終わってない段階で何言ってんだとなりそうなのでおとなしく粛々と進めます。

(執筆時間: 50分48秒)

Discussion