AtCoder Beginner Contest 382参加記
AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）に参加したので記録を残します。
今回は3完です。のんびり風呂に入っていたら遅れて、開始5秒前にRated登録しました。
A - Daily Cookie
足りないことはないので、単純に
fun main() {
val (n, d) = readln().split(" ").map { it.toInt() }
val s = readln()
println(s.count { it == '.' } + d)
}
B - Daily Cookie 2
最も右にあるクッキーを食べるという操作をそのままシミュレーションします。こちらの問題も足りないことはないのでその点は考慮しません。制約的に、毎回いちいち末尾から探してOK。
fun main() {
val (n, d) = readln().split(" ").map { it.toInt() }
val s = readln().toCharArray()
for(i in 0 until d) {
val index = s.lastIndexOf('@')
s[index] = '.'
}
println(s.joinToString(""))
}
C - Kaiten Sushi
少し頭を捻りました。寿司ごとに、それを食べるのは誰かを愚直に調べると間に合いません。なんとなく、先頭の人が有利であることに思いを馳せました。気に入った寿司は全部食べることができちゃうという…
それで、各人が食べる寿司はどれかという方向で考えることを思いつきました。既に誰かが食べた寿司を他の誰かが再度食べることはあり得ないことから、寿司リストを作っていちいち調べるとしても、既に食べられた寿司は除外してしまえば実質線形時間でいけるんじゃね？と。
寿司のもともとの順番を別途保持しておけばソートしてしまっていいです。美味しい順から食べるだけ食べさせて位置を記録、食べられた寿司は削除、食べたくない寿司が出現したら次の人、というのを1人目からやっていけば実質線形時間です。削除を高速に実行する必要はありますが。
ソートしてから後ろを見ていって、末尾を削除するようにすれば高速です。このアルゴリズムだと削除するのは必ず末尾です。
import java.io.PrintWriter
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val b = readln().split(" ").map { it.toInt() }
val sushi = b.mapIndexed { index, i -> Sushi(index, i) }
.sortedByDescending { it.b }
.toMutableList()
val min = a.min()
val ans = IntArray(m)
for(i in sushi.size - 1 downTo 0) {
if(sushi[i].b < min) {
ans[sushi[i].index] = -1
sushi.removeLast()
} else {
break
}
}
sushi.sortBy { it.b }
for(i in a.indices) {
for(j in sushi.size - 1 downTo 0) {
if(sushi[j].b >= a[i]) {
ans[sushi[j].index] = i + 1
sushi.removeLast()
} else {
break
}
}
}
val out = PrintWriter(System.out)
ans.forEach {
out.println(it)
}
out.flush()
}
data class Sushi(
val index: Int,
val b: Int,
)
上記では誰も食べない寿司の考慮を入れていましたが、今思えば別にいらなかったですね。
D - Keep Distance
これは解けませんでした。
コンテスト後のTLでは再帰DFSで解いたと言っている人が多くて、たしかにそうだなと… なぜ思いつかなかったのか。
ただ、実際解いてみるとけっこうTLEに苦しめられました。ちゃんと枝刈りしないといけないのと、枝刈りして無駄な探索はしてないはずなのにそれでもTLEが出てちょっと困りました。
最終的に通ったのは以下のコードです。
import java.io.PrintWriter
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val ans = mutableListOf<String>()
dfs(1, n, m, IntArray(n), 0, ans)
val out = PrintWriter(System.out)
out.println(ans.size)
ans.forEach {
out.println(it)
}
out.flush()
}
fun dfs(start: Int, n: Int, m: Int, array: IntArray, index: Int, ans: MutableList<String>) {
if(index == n) {
ans.add(array.joinToString(" "))
return
}
for(i in start..m) {
if(index != n - 1 && i + 10 > m) {
break
}
array[index] = i
dfs(i + 10, n, m, array, index + 1, ans)
}
}
通らなかったコードだと、個別の数列を可変長配列（MutableList）で扱っていました。Kotlinの場合、これだとオートボクシング/アンボクシングでいちいちインスタンス生成が発生します。それのせいでTLEって個人的にはあんまり見たことなかったんですが、今回はそれが直撃しましたね。IntArray（Javaだとint[]）だとオートボクシング/アンボクシングは発生しません。IntArrayにしたら通りました。
通らなかったコード
感想
オートボクシング/アンボクシングでやられるとは… しかしちょっと楽しかった。
Discussion