🌟
AtCoder Beginner Contest 376参加記

2024/10/20に公開
AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY）に参加したので記録を残します。
https://atcoder.jp/contests/abc376

 A - Candy Buttonこういう状態遷移を考えるのは苦手で詰まりました。最初とそれ以外で分けて考えたほうがよかったですね。ボタンを押した時（最初以外）、前回飴をもらった時間からその時点の時間を引いた値がC以上かどうかを見ればよかったです。

最初にボタンを押した時は無条件にもらうようにします。
fun main() {
    val (n, c) = readln().split(" ").map { it.toInt() }
    val ts = readln().split(" ").map { it.toInt() }

    var ans = 0
    var time = 0
    var before = 0
    for(t in ts) {
        if(t == ts.first()) {
            ans++
            before = t
            continue
        }

        val diff = t - before
        if(diff >= c) {
            ans++
            before = t
        }
    }

    println(ans)
}
https://atcoder.jp/contests/abc376/submissions/58938517

 B - Hands on Ring (Easy)右周りか左回りかの2通りしか方法がなく、さらに片方は可能でもう片方は不可能なのが明らかです。なので単純に両方試して操作が完了できたほうを採用すればよさそう。計算で解こうとすると絶対ミスるので、愚直にシミュレーションしました。
1とNをまたぐパターンが面倒ですね。そこでListを作って、Collections.rotate()で順繰りに見ることができるようにしました。
import java.util.*

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

    val ht = List(q) {
        val input = readln().split(" ")
        val h = input.first().first()
        val t = input.last().toInt()

        h to t
    }

    val list = (1..n).toMutableList()

    var ans = 0
    var l = 1
    var r = 2
    for((h, t) in ht) {
        val start: Int
        val other: Int
        if(h == 'R') {
            start = r
            other = l
        } else {
            start = l
            other = r
        }

        val count = tryCalc(start, t, other, 1, list)
        if(count != -1) {
            ans += count
        } else {
            ans += tryCalc(start, t, other, -1, list)
        }

        if(h == 'R') {
            r = t
        } else {
            l = t
        }
    }
    println(ans)
}

fun makeList(target: Int, list: MutableList<Int>) {
    while (true) {
        if(list.first() == target) {
            return
        }

        Collections.rotate(list, 1)
    }
}

fun tryCalc(start: Int, end: Int, other: Int, dist: Int, list: MutableList<Int>): Int {
    makeList(start, list)

    var count = 0
    while (true) {
        if(list.first() == end) {
            return count
        }

        Collections.rotate(list, dist)

        if(list.first() == other) {
            return -1
        }

        count++
    }
}
https://atcoder.jp/contests/abc376/submissions/58951993

 C - Prepare Another Box降順ソートして貪欲でできそうだと思いました。大きいおもちゃほど厄介なのでそっちを優先して処理すればいいだろうと。おもちゃも箱も大きさで降順ソートして入れられるかを見ていって、入れられなかったら一度だけ購入します。購入後に入れられないことが発生したら達成不可。入れられないことが一度も達成しなかったら、一番小さいおもちゃと同じ大きさの箱を買ってそれが答えです。
実装方法としては、ちょっと乱暴ですが途中で購入したら箱リストにそれを挿入します。挿入には線形時間かかりますが、最大でも1回しか実行しないので問題なし。
入れられないことが一度も発生しない場合の添字の管理をミスって1ペナ。
fun main() {
    val n = readln().toInt()
    val a = readln().split(" ").map { it.toInt() }
        .sortedDescending()
    val b = readln().split(" ").map { it.toInt() }
        .sortedDescending().toMutableList()

    var ans = -1
    for(i in a.indices) {
        if(i == a.size - 1 && a.size != b.size) {
            ans = a.last()
            break
        }

        if(a[i] <= b[i]) {
            continue
        }

        if(ans != -1) {
            ans = -1
            break
        }

        ans = a[i]
        b.add(i, a[i])
    }

    println(ans)
}
https://atcoder.jp/contests/abc376/submissions/58964314

 D - CycleUnion-Find…は無向グラフでないと使えないか。
DFSで見ていって、1を含む閉路を見つけたらその時点の答えを保持、その辺を削除して探索続行、みたいなことを考えたのですがこれだといろんな意味でダメそうでした。

 感想ABが難しかったですね。でもBみたいなのはわりと好き。Dは、今の私が解けないのはしょうがないですね。むしろCで1ペナ出したことのほうが悔しい感じ。
A - Candy Button

B - Hands on Ring (Easy)

C - Prepare Another Box

D - Cycle

感想

Discussion
