📝

AtCoder Beginner Contest 343参加記

2024/03/03に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 343に参加したので記録を残します。
https://atcoder.jp/contests/abc343

今回は4完ですが、Dまでの難易度は低めのわりに時間がかかってしまいました。

A - Wrong Answer

0から9まで一通り調べて、条件を満たす最初の値を出力しました。
サンプルがあてにならないですが、まあ大丈夫。

fun main() {
    val (a, b) = readln().split(" ").map { it.toInt() }

    println((0..9).toList().filter { it != a + b }.first())
}

これでもよかったんですが。

fun main() {
    val (a, b) = readln().split(" ").map { it.toInt() }

    println((0..9).toList().first { it != a + b })
}

B - Adjacency Matrix

問題文を見て少しギョッとしましたが、よく見たら一通り見て1だったらその位置を出力するだけでした。

fun main() {
    val n = readln().toInt()
    val a = List(n) {
        readln().split(" ").map { it.toInt() }
    }

    for(i in 0 until n) {
        val list = mutableListOf<Int>()
        for(j in 0 until n) {
            if(a[i][j] == 1) {
                list.add(j + 1)
            }
        }
        println(list.sorted().joinToString(" "))
    }
}

C - 343

$x^3$ が $N$ を超える場合の $x$ は見なくていいので、 $10^6$ まで探索すればいいというのはすぐにわかりました。
しかし、各数値が条件を満たすかどうかの判定になぜか手間取りました。cbrtを使えば三乗根を求めることができるのですが、浮動小数点が出てくるのが嫌で他の方法でやろうとして時間を無駄にしました。
結局cbrtを使っても問題なかったです…

import kotlin.math.abs
import kotlin.math.cbrt

fun main() {
    val n = readln().toLong()

    var ans = 1L
    for(i in 1L..n) {
        val num = i * i * i
        if(num > n) {
            break
        }

        val c = cbrt(num.toDouble()).toLong()

        if(c * c * c == num) {
            val s = num.toString().toList()
            if(s.reversed() == s) {
                ans = num
            }
        }
    }

    println(ans)
}

D - Diversity of Scores

各選手の時間ごとの得点を記録して調べていけばいいですが、愚直に調べると間に合いません。そこで、各得点の選手が何人いるかを記録することを考えます。
最初は0点の選手が $N$ 人というところから始めて、 $A_i$ と $B_i$ が入力されるたびに変更前の得点の人数が1人減り、変更後の得点の人数が1人増える、というのをMapに記録してきます。0人になった得点については削除するようにすれば、単純にMapの要素数が答えになります。

C問題くらいの難易度で難しくはなかったのですが、凡ミスで1ペナしました。不甲斐ないです。

import java.io.PrintWriter

fun main() {
    val (n, t) = readln().split(" ").map { it.toInt() }
    val ab = listOf(0L to 0L) + List(t) {
        val (a, b) = readln().split(" ").map { it.toLong() }
        a to b
    }

    val bucket = LongArray(n + 1)

    val map = mutableMapOf<Long, Int>()
    map[0] = n

    val out = PrintWriter(System.out)
    for(i in 1..t) {
        val (a, b) = ab[i]
        val current = bucket[a.toInt()]
        bucket[a.toInt()] += b

        map[bucket[a.toInt()]] = map.getOrDefault(bucket[a.toInt()], 0) + 1

        map[current] = map[current]!! - 1
        if(map[current] == 0) {
            map.remove(current)
        }

        out.println(map.size)
    }

    out.flush()
}

bucket[a.toInt()]は変数に入れて管理すべきだったかも。

E - 7x7x7

順位表を見て、EF逆転していたのでEは見てません。

F - Second Largest Query

こういう区間の更新と取得が入り交じるようなものはセグ木を使う、というのはなんとなく知っていたのですが、実際にセグ木を使ったことがないので無理でした。

感想

CDについて難易度の割に時間がかかったのと、Dについてはペナルティまでもらったので残念な結果に終わったと思ったのですが、それでもなぜかレートとしては微増で落ち着きました。
この結果で微増なら、CDを満足のいくスピードで解けていたら緑になっていた可能性が…

Cに時間がかかったのは浮動小数点数を雰囲気でしか理解していないことで判断ミスをした結果とも言えそうですし、特に不調を感じていたわけでもないので普通に実力を出せた上でこの結果なんでしょうね。頑張ります…

微増とはいえ緑に近づきはしたので、まだまだチャンスありということで前向きにやっていきます。

ところで一応セグ木はちゃんと勉強したほうがいいのかな… そりゃ間違いなく勉強したほうがいいですが、優先度としてはどれくらいなのかな。
（執筆時間: 23分35秒）