AtCoder Beginner Contest 348参加記
トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）に参加したので記録を残します。
今回は3完です。12分くらいなのでまあまあ早解き成功かな…
A - Penalty Kick
3の倍数かどうか判定して出力する文字を変えるだけです。都度printしてもよかったけどなんとなくこうなりました。
fun main() {
val n = readln().toInt()
val sb = StringBuilder()
for(i in 1..n) {
if(i % 3 == 0) {
sb.append("x")
} else {
sb.append("o")
}
}
println(sb)
}
B - Farthest Point
2つ選ぶ組み合わせを全探索しました。本来は距離については平方根をとる必要がありますが、比較するだけならなくてもOK。（浮動小数点数を使いたくなかったので）
「ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力してください。」というのを見てなかったことに気づきましたが、番号が小さいほうから見ているのと、同値の場合は番号を更新していないので結果的に問題なかったです。危うい…
import kotlin.math.max
import kotlin.math.sqrt
fun main() {
val n = readln().toInt()
val xy = List(n) {
val (x, y) = readln().split(" ").map { it.toInt() }
x to y
}
for(i in 0 until n) {
var maxDist = 0
var ans = 0
for(j in 0 until n) {
if(i == j) {
continue
}
val (x1, y1) = xy[i]
val (x2, y2) = xy[j]
val xx = (x2 - x1) * (x2 - x1)
val yy = (y2 - y1) * (y2 - y1)
val dist = (xx + yy)
if(dist > maxDist) {
ans = j + 1
}
maxDist = max(maxDist, dist)
}
println(ans)
}
}
C - Colorful Beans
色ごとの最小値を求めて、その中での最大値を出力します。色ごとの最小値はmapで管理して、mapが保持する値リストの中の最大値が答えですね。
特に難しくはない感じ。
import kotlin.math.min
fun main() {
val n = readln().toInt()
val ac = List(n) {
val (a, c) = readln().split(" ").map { it.toInt() }
a to c
}
val map = mutableMapOf<Int, Int>()
for((a, c) in ac) {
val aa = map.getOrDefault(c, Int.MAX_VALUE)
map[c] = min(a, aa)
}
println(map.map { it.value }.max())
}
D - Medicines on Grid
これは全然解けなかったです。とりあえず愚直にやってみようかと思ったけどそれすら実装しきれず撃沈。再帰DFSだと書きやすいけど遅すぎてダメ、非再帰DFSで書き直そうとしたけどうまく書けず。
というか、よく見ると到達できなかった場合にNoを出力するのを忘れてるし、それを直してもまだWAが出るし、とグダグダでした。
到達可能かどうかってだけならDFSでいいのですが、体力管理を考えると最短距離を求める必要があるのでDFSではダメっぽいですね。それに解説を見ると、いかにも愚直ではダメそうに見える。
薬の位置のグラフを作るというのが想定解っぽいのですが、なぜそうするといいのかよくわかっていません。難しい…
感想
Dはそれなりに難しかったようなのでCまで早解きでも緑パフォが出ました。喜んでいいのかわからないですが、Dが解ける可能性はなかったと思うのでとりあえずベストは尽くせたことになるのか…
Dは現時点だと解説を理解していないですが、理解不能ってほどではない気がするので少し粘ってみようかと思います。
（執筆時間: 21分56秒）
Discussion