AtCoder Beginner Contest 305参加記（A～C）
京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)に参加したので記録を書いておきます。
今回も爆死してこれで3連敗となります…
Cが解けなくて2完に終わったほか、ABでも異様に時間がかかったことでパフォが185というとっても素敵な数値になりました。
A - Water Station
給水所は21箇所と決まっているので、
import kotlin.math.abs
fun main() {
val n = readLine()!!.toInt()
if(n % 5 == 0) {
println(n)
} else {
var min = Int.MAX_VALUE
var ans = min
for(i in 0 until 21) {
val diff = abs(i * 5 - n)
if(diff < min) {
ans = i * 5
min = diff
}
}
println(ans)
}
}
なんか全くといっていいほど頭が働かず、これに17分もかかりました。
B - ABCDEFG
各数値がA～Fに紐づくものとして計算して求めました。
fun main() {
val (p, q) = readLine()!!.split(" ").sorted()
val array = arrayOf(3, 1, 4, 1, 5, 9)
val s = "ABCDEFG"
val start = s.indexOf(p)
val end = s.lastIndexOf(q)
var ans = 0
for(i in start until end) {
ans += array[i]
}
println(ans)
}
C - Snuke the Cookie Picker
解けなかったC問題です。やるだけの問題なので、実装方針は立っていたものの実装できなかったということで、かなりマズい感じです…
方針としては、まず欠けた位置の高さを求めます。次にその高さで'#'の左端と右端を求めます。それで左端から右端までの間に'.'があったらその位置が答えとなる、という感じです。
もちろんこれだけだとダメで、左端か右端が欠けている場合の考慮も必要です。前のステップで'.'が見つからなかったら端っこが欠けているパターンなので、欠けているのが左端なのか右端なのかを調べます。左端の左上か左下が'#'なら左端が欠けている、そうでなければ右端が欠けている、としようとしています。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = List(h) {
readLine()!!
}
var c = 0
var min = Int.MAX_VALUE
for(i in 0 until h) {
if(s[i].indexOf("#") < 0) {
continue
}
val count = s[i].count { it == '#' }
if(count < min) {
min = count
c = i
}
}
val start = s[c].indexOf("#")
val end = s[c].lastIndexOf("#")
for(i in start..end) {
if(s[c][i] == '.') {
println("${c+1} ${i+1}")
return
}
}
val diff = if(c == 0) {
1
} else {
-1
}
if(start == 0) {
println("${c+1} ${end+2}")
return
}
if(s[c + diff][start - 1] == '#') {
println("${c+1} $start")
return
}
println("${c+1} ${end+2}")
}
上記の実装だと左上を調べる際に範囲外を参照しないようにしていますが、そのあとに左下を調べていないので、左上が欠けているケースで落ちています…
コンテスト後に上記方針のままで修正したのが以下です。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = List(h) {
readLine()!!
}
var c = 0
var min = Int.MAX_VALUE
for(i in 0 until h) {
if(s[i].indexOf("#") < 0) {
continue
}
val count = s[i].count { it == '#' }
if(count < min) {
min = count
c = i
}
}
val start = s[c].indexOf("#")
val end = s[c].lastIndexOf("#")
for(i in start..end) {
if(s[c][i] == '.') {
println("${c+1} ${i+1}")
return
}
}
val diff = if(c == 0) {
1
} else {
-1
}
if(start == 0) {
println("${c+1} ${end+2}")
return
}
if(s[c + diff][start - 1] == '#') {
println("${c+1} $start")
return
}
if(c != h - 1 && s[c + 1][start - 1] == '#') {
println("${c+1} $start")
return
}
println("${c+1} ${end+2}")
}
これで通りましたが、実装方針としては良くないと思いました。実装しきれないのも問題なのですが、そもそも実装が面倒でバグを埋め込みやすい方針となっているのも問題です。斜めだと縦と横を両方同時に考えないといけないし、配列の範囲外参照を防ぐための場合分けも多く発生します。
それでも実装しきれるくらいの力があればいいのですが、残念ながらそれほどの力はないと認めるしかありません。
以前、以下のようなことを書いていたのですが…
「自分は添え字操作が苦手。特に斜めはヤバい」ということを認識しておこうと思います。
うん、全く教訓が生きていませんね。完全に忘れてました…
斜めを見ることなく実装するように書き直したのが以下です。
長方形の範囲を特定すれば、あとはその中で全探索して'.'が見つかったらその位置が答えとなります。最初からこうすればよかったです。ほんと。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = List(h) {
readLine()!!
}
val u = s.indexOfFirst { it.contains('#') }
val d = s.indexOfLast { it.contains('#') }
var l = -1
for(j in 0 until w) {
for (i in 0 until h) {
if(s[i][j] == '#') {
l = j
break
}
}
if(l != -1) {
break
}
}
var r = -1
for(j in w - 1 downTo 0) {
for (i in h - 1 downTo 0) {
if(s[i][j] == '#') {
r = j
break
}
}
if(r != -1) {
break
}
}
for(i in u..d) {
for(j in l..r) {
if(s[i][j] == '.') {
println("${i+1} ${j+1}")
}
}
}
}
感想
最近以下のツイートを見て、「へぇ～」と思ったのですが
強い子ほど、単に注意力だけじゃなくて、バグりにくい実装方針や実装方法を選ぶのが上手だね
今回の爆死を経て、すごく身に沁みるように感じました…
注意力も鍛えないといけないですが、そもそも注意しなくてもバグらせにくい方法を考えるほうがさらに重要と思いました。それも、短時間で思いつく必要があります。
上で書いた教訓を忘れていたように、ここで教訓を書いただけだとあんまり印象に残らないのですよね。なので、さすがに今回は重く受け止めて練習をしようと思いました。
AtCoderの問題をジャンルで分類してくださっている方がいて、グリッドに分類されている問題を一通り解いていこうと思います。
それも、斜めを見なくて済む、バグらせにくい方法をできるだけ考えてやってみます。
なかなか厳しい状況ですが、特に心が折れてはいないので地道にやって改善していきます。
まあ、Cが解けなかったことに対する対処としては上記でよさそうですが、ABで異様にもたついたことについてはなんか他に原因があるような気がするんですけどね。なんか21時になってコンテスト開始のダイアログが出た時点では全然エンジンがかかっていなかった感があり。
そちらについては原因がよくわからないので一旦置いておきます。
（執筆時間: 45分43秒）
Discussion