🦔

AtCoder Beginner Contest 358参加記

2024/06/17に公開

AtCoder

競プロ

tech

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)に参加したので記録を残します。
https://atcoder.jp/contests/abc358

本戦出場資格がないので、単純にABCとしての参加です。先週参加できなかったので2週間ぶりですね。今回は4完ですが、Dがかなり解かれていたのでギリギリ冷えを免れたくらいの成績です。

なお、今回のABCは某ランドモチーフな雰囲気ですね。

A - Welcome to AtCoder Land

そのままやるだけです。splitしなくていい気もしたのですが、一応しました。

fun main() {
    val (s, t) = readln().split(" ")
    if(s == "AtCoder" && t == "Land") {
        println("Yes")
    } else {
        println("No")
    }
}

B - Ticket Counter

こういう状態遷移を書くのは本当に苦手で、一旦飛ばしました。Cを解いてから戻ってきて解きました。

まず、遅れがない理想的なケースを考えました。その場合は各答えは $A$ の倍数になります。それに対して、どれくらいの遅れが発生するかという感じで考えました。
理想的な場合の値よりも $T_i$ が遅ければその差分が遅れとなるので、そのように計算してきました。一度発生した遅れが解消することはなく、そのまま足されていきます。

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

    var delay = 0L
    var ideal = 0L
    for(i in t.indices) {
        if(t[i] > ideal + delay) {
            delay += t[i] - (ideal + delay)
        }

        ideal += a
        println(ideal + delay)
    }
}

delayはidealに足し込んでしまったほうがよかったかも。

C - Popcorn

制約が小さいので全探索でいけそう。たとえば、一旦すべての店に訪問すると考えて、訪問順を順列として全列挙する、順番に買えるものは全部買って、全ての種類が手に入った時点で切り上げる、でできそうだと思いました。

順列全列挙はKotlinには標準では用意されていないので、以前自作したものを使いました。

import kotlin.math.min

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

    val list = (0 until n).toMutableList()
    val permutation = Permutation(list)
    var ans = Int.MAX_VALUE

    permutation.forEach { numbers ->
        val set = mutableSetOf<Int>()
        var count = 0

        for(i in numbers) {
            val si = s[i]
            for(j in si.indices) {
                if(si[j] == 'o') {
                    set.add(j)
                }
            }
            count++
            if(set.size == m) {
                break
            }
        }
        ans = min(ans, count)
    }
    println(ans)
}

class Permutation<T>(private val list: MutableList<T>) {
    private val queue = ArrayDeque(list)

    fun forEach(action: (MutableList<T>) -> Unit) {
        forEach(0 ,0, action)
    }

    fun toList(): List<List<T>> {
        val list = mutableListOf<List<T>>()
        forEach {
            list.add(it.toList())
        }
        return list.toList()
    }

    private fun forEach(count: Int, layer: Int, action: (MutableList<T>) -> Unit) {
        if(count == list.size) {
            action(list)
            return
        }

        for(i in count until list.size) {
            val elem = queue.removeFirst()
            list[layer] = elem
            forEach(count + 1, layer + 1, action)
            queue.add(elem)
        }
    }
}

通りはしたものの、実行時間がギリギリ！

考えてみると $10!$ は $3,628,800$ だし、それに100がかかるので $362,880,000$ （3億6288万）通りになりますね。むしろよく通ったな…

なお、想定解としてはbit全探索だったようです。各店について訪れる、訪れないの2つの状態を考えるということで。たしかに、なんで思いつかなったんだろう。

D - Souvenirs

あり得る買い方の全探索は間に合いません。 $M$ のほうについて考えてみると、ソートして貪欲でいけると気づきました。
つまりソートした後の $B_1$ について、それを満たす買い方としては $A_i$ のiうち $B_1$ 以上のうちの最小値を採用すると考えます。これは操作としては $A_i$ も $B_i$ もソートして、 $A_1$ を取り出し、 $B_1$ 以上であれば採用して $B_1$ を削除、そうでなければ捨てて $B_1$ は削除しない、を繰り返します。
$B_i$ が空になればその時点の合計値が答え、 $A_i$ が空になった時点で $B_i$ が空でなければ達成不可能、となります。

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

    val b = readln().split(" ").map { it.toInt() }
        .sorted()
        .toArrayDeque()

    var ans = 0L

    while (a.isNotEmpty() && b.isNotEmpty()) {
        val aFirst = a.removeFirst()
        val bFirst = b.first()

        if(aFirst >= bFirst) {
            ans += aFirst
            b.removeFirst()
        }
    }
    if(b.isEmpty()) {
        println(ans)
    } else {
        println(-1)
    }
}

fun List<Int>.toArrayDeque(): ArrayDeque<Int> {
    return ArrayDeque(this)
}

かなり多く解かれていましたが、個人的にはけっこう難しいと感じてしまいました。

感想

まあ精進できていないので、冷えなかっただけでも大儲けですね。あとDが簡単（たぶん？）だったとはいえ4完できてよかったです。
少し時間に余裕ができそうなので、今後はもう少し精進したいところです。
（執筆時間: 27分29秒）

A - Welcome to AtCoder Land

B - Ticket Counter

C - Popcorn

D - Souvenirs

感想

Discussion