AtCoder Beginner Contest 304参加記（A～C）
東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）に参加したので記録を書きます。
今回は2完（しかも遅い）とかなり残念な結果に。コンテスト自体がUnratedになってしまったのでレーティングは下がらなかったものの、むしろ戒めとするために下がってほしかったまであります。
A - First Player
起点となる人を探して、まず起点から末尾まで出力、それから先頭から起点の一つ前まで出力という二段階で処理しました。添え字を計算で求めるのが正攻法かもしれないですが、絶対ミスるので可能な限り避けたく…
fun main() {
val n = readLine()!!.toInt()
val sa = List(n) {
val (s, a) = readLine()!!.split(" ")
s to a.toInt()
}
val min = sa.minBy { it.second }
val index = sa.indexOf(min)
for(i in index until n) {
println(sa[i].first)
}
for(i in 0 until index) {
println(sa[i].first)
}
}
B - Subscribers
全部場合分けしようとしたり、切り捨てというのをなぜか桁自体を消し去るのと勘違いしたり、などしてグダグダでした。
最終的にはシンプルな実装に落ち着きましたが、だいぶ時間を食いました。
fun main() {
val n = readLine()!!.toInt()
val s = n.toString()
if (n <= 1000 - 1) {
println(n)
} else {
println(s.substring(0, 3) + "0".repeat(s.length - 3))
}
}
C - Virus
愚直にやろうとしてTLEを繰り返して、結局解けませんでした。
import kotlin.math.sqrt
fun main() {
val (n, d) = readLine()!!.split(" ").map { it.toInt() }
val xy = List(n) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() }
x to y
}
val eps = 1e-10
val ans = BooleanArray(n)
ans[0] = true
val dd = d.toDouble()
val map = mutableMapOf<Int, Double>()
val new = mutableSetOf<Int>()
var i = 0
while(i < n) {
val flg = i in new
if(!ans[i] && !flg) {
i++
continue
}
if(flg) {
new.remove(i)
}
val a = xy[i]
var j = 0
while (j < n) {
if(i == j) {
j++
continue
}
if(ans[j]) {
j++
continue
}
val b = xy[j]
val sum = double(a.first - b.first) + double(a.second - b.second)
val dist = if(map.containsKey(sum)) {
map[sum]!!
} else {
val tmp = sqrt((sum).toDouble())
map[sum] = tmp
tmp
}
if(dist - dd < eps) {
ans[j] = true
new.add(j)
i = 0
j = 0
} else {
j++
}
}
i++
}
ans.forEach {
if(it) {
println("Yes")
} else {
println("No")
}
}
}
fun double(i: Int): Int {
return i * i
}
このやり方だと、感染者が出た場合はそこを起点とする探索をまた新たに実行しないといけなくて計算量が膨れ上がりTLEとなりました。
実際には、グラフの問題としてとらえればよかったようです。感染があり得る距離の場合だけ辺があるグラフを作って、起点の1と同じ連結成分に含まれればよかったと。
辺を作る時点では感染しているかどうかは考えずに距離だけを見て処理すればよく、実際感染するかどうかは1と同じ連結成分に含まれるかどうかを調べる段階で判明すると。
fun main() {
val (n, d) = readLine()!!.split(" ").map { it.toInt() }
val xy = List(n) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() }
x to y
}
val graph = Array(n) { mutableListOf<Int>() }
for(i in 0 until n) {
val a = xy[i]
for(j in i + 1 until n) {
val b = xy[j]
val dist = ((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second))
if(dist <= d * d) {
graph[i].add(j)
graph[j].add(i)
}
}
}
val seen = BooleanArray(n)
val queue = java.util.ArrayDeque<Int>()
queue.add(0)
val ans = BooleanArray(n)
ans[0] = true
while (queue.isNotEmpty()) {
val v = queue.removeFirst()
if(seen[v]) {
continue
}
seen[v] = true
for(node in graph[v]) {
ans[node] = true
queue.add(node)
}
}
ans.forEach {
if(it) {
println("Yes")
} else {
println("No")
}
}
}
距離の判定と感染するかどうかの判定をごっちゃにしたのが良くなかったですね。分けて考えれば、「グラフを作る」「起点から辿れる範囲を全部探索する」だけで済むので…
感想
今回のCは解けるべき問題だったと思うので、残念ですね。一時休止していたのが思ったより響いてそう。復調まで時間がかかりそうだけど、続けていけばなんとかなるでしょう。焦らずに続けていきます。
それにしても、グラフは特に苦手意識はなかったんですけどね。まあ、直接的にグラフが入力される問題ばっかり解いていて、自分でグラフを作るような問題をあまり解いたことがなかったのもあるかもしれません。何にせよまだまだ解いた問題数が足りない。
（執筆時間: 33分29秒）
Discussion