💭

AtCoder Beginner Contest 351参加記

2024/04/28に公開

AtCoder

競プロ

tech

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

今回は2完です。Cはどうやら別に難しくはなく、多くの人に解かれていた中で自分は解けなかったので大爆死ですね…

A - The bottom of the ninth

問題文はちょっと長いけど、やることは単純です。それぞれの合計値の差を求めるとそれが点差なので、それを足せば同点になります。勝つ必要があるので、それに1を足します。

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

    println(a.sum() - b.sum() + 1)
}

B - Spot the Difference

グリッドを探索して、値が異なる位置を探すだけです。異なる箇所は1箇所しかないので、見つけたら即終了でOK。

fun main() {
    val n = readln().toInt()
    val a = List(n) {
        readln()
    }
    val b = List(n) {
        readln()
    }

    for(i in 0 until n) {
        for(j in 0 until n) {
            if(a[i][j] != b[i][j]) {
                println("${i+1} ${j+1}")
                return
            }
        }
    }
}

C - Merge the balls

これが解けませんでした。

大きさが $2^{A_i}$ となっていますが、 $A_i$ は大きいので実際に求めること実質できません。しかし、これは単純に $A_i$ のまま扱えばいいですね。操作3でマージする際は同じ数を2つ足す、つまり2倍することになり、2倍するということはここで扱う値（指数）は1増やせばいいということになります。
そこまでは良かったですが、そこから先で詰まりました。結果的にはただ愚直に列を作っていくだけでよかったのですが、例1にもあるようにマージして追加した時にそれが連鎖して何度も操作が発生する場合があり、これの処理回数が非常に多くなるのではないかと思って、その方法は無理だと判断してしまいました。
なんとなく $O(N^2)$ くらいの計算量になるのではと思ってしまい。ただ、この操作をした時は列の値は1つ減ります。1つも減らないのであればたしかに $O(N^2)$ になりますが、実際には操作するたびにどんどん1つずつ減っていくわけなので、少なくとも $O(N^2)$ にはならないですね…
場合によっては、列にある全ての要素に対して連鎖的に操作が発生することもありますが、それが終わった後には列の値は1つまで減っているので、次の操作でまた同じことが発生することはない、みたいに考えれば気づきやすかったのかな…
まあ $O(N^2)$ にはならないとしても、じゃあ実際どれくらいの処理回数になるのかというと、正直イメージできません。このように計算量の見積もりができてないのが敗因でしたね。

コンテスト後に通したのは以下です。ほんとにやるだけだ…

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

    val deque = ArrayDeque<Int>()

    for(i in a.indices) {
        deque.add(a[i])

        while (deque.size > 1) {
            val c = deque.removeLast()
            val b = deque.removeLast()

            if(b != c) {
                deque.add(b)
                deque.add(c)

                break
            }

            deque.add(b + 1)
        }
    }

    println(deque.size)
}

感想

800あったレートが一気に760まで下がってしまいました。緑維持ができるとは思ってなかったですが、ここまで派手にやらかすとは思ってなかったですね…
まあ、グリッドを探索するだけの問題が解けなくて灰パフォとかは以前もあって、このように致命的な穴がちらほらあるのが私なんだろうなあ…😇

見つけるたびに埋めていくしかないですね。とりあえず計算量の見積もりの練習をしたいところです。とりあえずアルゴ式の計算量のところの練習問題をやってみるかな。

あと、この問題を思い出しました。

これはたしか愚直にスタックで操作するだけで解けるのですが、当時なぜそれで間に合うのかわからなかったんですよね。こういう感じで「実は愚直で間に合う」系の問題を他にも色々見てみたいですねぇ。どうやって探せばいいか不明ですが。とりあえずこの問題についてはもう一回見てみたいところ。
（執筆時間: 40分41秒）

A - The bottom of the ninth

B - Spot the Difference

C - Merge the balls

感想

Discussion