✨

AtCoder Beginner Contest 339参加記（A～C）

2024/02/04に公開

AtCoder

競プロ

tech

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）に参加したので記録を残します。
https://atcoder.jp/contests/abc339

今回も3完です。前回のJPRSコンは非常に残念な結果だったので頑張りたかったですが、今回も（前回よりはいいですが）ちょっと残念な感じでした。

A - TLD

splitしてから最後の要素を出力すればOKです。なにげに、ファイルの拡張子を取得するとかでこういう実装を実務でやることがありますね。

fun main() {
    val s = readln()
    println(s.split(".").last())
}

B - Langton's Takahashi

実際に移動をシミュレーションすればいいです。実装はちょっと面倒ですね。グリッド系の実装は面倒になりがち。こういうの苦手なので、ちょっと時間がかかりました。以前の私なら沼ってたかも…
向きは、その向きの場合に移動する縦横のそれぞれの増分を配列に持たせて順繰りで見ていくようにしました。こういう工夫は、以前グリッド系が解けなくて死んだ反省に基づくものです…ｗ

その配列とか、はみ出て反対側に移動する場合の処理とかは、愚直にそのまま場合分けして書きました。余りをとるようにすれば場合分けしなくてもいいのですが、負の場合の余りの考慮漏れとかでバグらせるのが嫌だったので…
（公式の4分解説の動画で、C++だと注意という主旨のことが言われていましたが、Kotlinも同様です）

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

    val grid = List(h + 1) {
        CharArray(w + 1) { '.' }
    }

    val d = listOf((-1 to 0), (0 to 1), (1 to 0), (0 to -1))
    var di = 0

    var i = 1
    var j = 1

    for(ii in 1..n) {
        if(grid[i][j] == '.') {
            grid[i][j] = '#'
            di++
            if(di == 4) {
                di = 0
            }
        } else {
            grid[i][j] = '.'
            di--
            if(di == -1) {
                di = 3
            }
        }

        i += d[di].first
        if(i == 0) {
            i = h
        } else if(i == h + 1) {
            i = 1
        }

        j += d[di].second
        if(j == 0) {
            j = w
        } else if(j == w + 1) {
            j = 1
        }
    }

    grid.map { it.drop(1).joinToString("") }.drop(1).forEach {
        println(it)
    }
}

C - Perfect Bus

最初の人数を適当な数と仮定すると、実際に乗降車を計算していけばその数が条件を満たすかどうかはわかります。なので答えとしてあり得る数を全部試せばいいのですが、計算量的にもちろん間に合いません。
そこで、最初の人数として仮定する数を二分探索することを考えました。条件を満たす、満たさないには単調性があるので。二分探索の判定問題の計算量は $O(N)$ ですが、試す数を二分探索で絞れるので間に合いそう。

import kotlin.math.abs

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

    val isOk: (Long) -> Boolean = { x ->
        var current = x
        //println(x)

        var ret = true
        for(i in 0 until n) {
            current += a[i]
            if(current < 0L) {
                ret = false
                break
            }
        }
        ret
    }

    var current = binarySearch(-1, Long.MAX_VALUE / 10, isOk)

    for(i in 0 until n) {
        current += a[i]
    }

    println(current)
}

fun binarySearch(minNg: Long, maxOk: Long, isOk: (Long) -> Boolean): Long {
    var ng = minNg
    var ok = maxOk

    while(abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if(isOk(mid)) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

maxOk に渡している Long.MAX_VALUE / 10は適当です。十分に大きな数なら何でもいいだろうと。
まあこれでOKだったのですが、最初はLong.MAX_VALUEにしたことで結果が狂い、1ペナに繋がってしまいました…
abs(ok - ng)という計算をするので、Long.MAX_VALUEにするとオーバーフローします。うーん、アホすぎて笑えます。（笑えない）

なお、上記の二分探索結果で得られるのは最初に乗っていた人数の最小値ですが、答えとして出力するのは最後の時点で載っている人数なので、最後にもう一度配列を走査します。

ちなみに、二分探索とかしなくても以下のような解法でもよかったようですね。
最初に0人と仮定して計算をしていって負の数になったら、最初に乗っていたのはその絶対値を足した人数だったことにする、という解法です。計算としては、現在の人数が負の数になったら0に補正するだけ。
負の数になった際の絶対値を足していく計算をすれば最初に乗っていた人数の最小値が得られますが、答えとして出力するのは最後の時点の人数なので、そちらは計算する必要なし。Xを見るとこの解法を思いついた人はけっこういたっぽいのですが、私は全く思いつかなかったですね。

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

    var current = 0L
    for(i in 0 until n) {
        current += a[i]
        if(current < 0) {
            current = 0
        }
    }

    println(current)
}

感想

良い結果ではないですが、まあ最近はなかなか精進できていないのでしょうがないですね。以前の私ならBで沼ってたかもしれないですし、Cも二分探索解法すら思いつかず解けなかったかもしれないですし、と考えるとむしろよく耐えたのかもしれません。二分探索解法の着想は比較的最近解説ACした問題から得たので、それがなかったら実際解けなかった気がします。
結果としては残念でも、それでも以前の経験が生きたことで被害が比較的抑えられたということもわかりました。精進は裏切らないのですね…

ちょっとしばらくは競プロ以外のことに力を入れたいので当分こんな感じの結果が続くかもしれませんが、致命的な打撃を受けるようなことにならない程度にはちょろちょろ問題を解くのも並行したいと思います。
（執筆時間: 30分28秒）

A - TLD

B - Langton's Takahashi

C - Perfect Bus

感想

Discussion