AtCoder Beginner Contest 302参加記（A～B）
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)に参加したので記録を残します。
今回は1完という大爆死となりました。
A - Attack
基本は a / b ですが、割り切れない場合はさらにもう一回攻撃する必要があるのでそのようにしています。
fun main() {
val (a, b) = readLine()!!.split(" ").map { it.toLong() }
println(a / b + if(a % b == 0L) 0 else 1)
}
B - Find snuke
まさかの解けなかった問題です。やるだけの問題なのですが、斜めとか逆方向とかあって実装が面倒な感じでした。
通らなかったコードはひどすぎてアレなのでリンクだけ貼っておきます…
Stringのcontains()などを使って探していますが、contains()だと位置まではわからないので、なんかよくわからない計算で求めようとしていました。計算なんてろくにできないくせに何をやっているのか…
そういう便利メソッドに頼ってfor文を使った探索を避ける傾向はあります。ただ、この問題の場合は位置を出力するのだから、どう考えてもfor文を使ったほうがいいのになぜ思いつかなかったのか。
そもそも、斜めにいたっては探索範囲を網羅できていないという。ひどすぎ。
敗因はいろいろですが、特に重要なのは、ちゃんと方針が立つ前にそれっぽく実装に着手してしまった点かもしれません。
縦か横だけだったらそれでもよかったのでしょうけど、斜めのような厄介なパターンの場合にどうするのかはもう少し考えるべきでしたね。
実装先行だとなぜまずかったのかというと、実装方針が間違っていたことに途中で気づいても、一応途中まで実装したものがあるのでそれを破棄してやり直すという決断がなかなか勇気がいるためです。破棄せずに生かすことを考えてしまって、弥縫策みたいなことをしてごまかそうとしがちになります。そして、それはたいていうまくいかないという…
とはいえ、通常はB問題に対しては実装先行でも全然問題ないことが多いです。基本的にはB問題に対してそこまで時間をかけて考察する気が起こらないので、「実装方針を立ててから着手すべきだった」というのは後からだからこそ言えることでもあり…
そういう意味だと難易度推定のミスとも言えます。
まあ、あれこれ考えて教訓をくみ取ろうとしても、どうせ忘れちゃうんですよねぇ。教訓にすべきことが多すぎて覚えきれない。
なので今回は、「自分は添え字操作が苦手。特に斜めはヤバい」ということを認識しておこうと思います。
これは苦手だとすぐに判断できれば、ちゃんと考察してから着手するか、いっそ捨てるかという判断が冷静にできるはず…ということで。
なお、C問題はそこまで難しくなさそうだったので、Bを捨ててCに着手していればおそらく1完は免れたでしょうね…
なので競技という観点だとBを捨てる決断ができなかったのも問題なのですが、とはいえBは解くことが不可能な問題ってわけではなかったので、やはり単純にBを解けなかったことの方が問題と思いました。
最後に、コンテスト後にupsolveしたBのコードを載せておきます。
import kotlin.math.abs
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = List(h) {
readLine()!!
}
val target = "snuke"
for (i in s.indices) {
for(j in 0 until w) {
if(s[i][j] == 's') {
val ans = mutableListOf<Pair<Int , Int>>()
// 右
for (k in j until j + 5) {
if(k >= w) {
break
}
if(s[i][k] != target[k - j]) {
break
}
ans.add(i + 1 to k + 1)
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
// 左
for (k in j downTo j - 4) {
if(k < 0) {
break
}
if(s[i][k] != target[j - k]) {
break
}
ans.add(i + 1 to k + 1)
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
// 上
for (k in i downTo i - 4) {
if(k < 0) {
break
}
if(s[k][j] != target[abs(k - i)]) {
break
}
ans.add(k + 1 to j + 1)
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
// 下
for (k in i until i + 5) {
if(k >= h) {
break
}
if(s[k][j] != target[k - i]) {
break
}
ans.add(k + 1 to j + 1)
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
// 右上
var diff = 0
for (k in i downTo i - 4) {
if(k < 0 || j + diff >= w) {
break
}
if(s[k][j+diff] != target[abs(k - i)]) {
break
}
ans.add(k + 1 to j + diff + 1)
diff++
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
diff = 0
// 左上
for (k in i downTo i - 4) {
if(k < 0 || j - diff < 0) {
break
}
if(s[k][j-diff] != target[abs(k - i)]) {
break
}
ans.add(k + 1 to j - diff + 1)
diff++
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
diff = 0
// 右下
for (k in i until i + 5) {
if(k >= h || j + diff >= w) {
break
}
if(s[k][j+diff] != target[k - i]) {
break
}
ans.add(k + 1 to j + diff + 1)
diff++
}
if(ans.size == 5) {
ans.println()
return
}
ans.clear()
diff = 0
// 左下
for (k in i until i + 5) {
if(k >= h || j - diff < 0) {
break
}
if(s[k][j-diff] != target[k - i]) {
break
}
ans.add(k + 1 to j - diff + 1)
diff++
}
if(ans.size == 5) {
ans.println()
return
}
}
}
}
}
fun MutableList<Pair<Int, Int>>.println() {
this.forEach {
println("${it.first} ${it.second}")
}
}
もうちょっと共通化できるのではないかとも思ったのですが、そのまま書いてしまいました。
アルゴリズムとしては、sを発見したらそこから周囲の8方向をそれぞれ探索するというものに変わっています。元のアルゴリズムよりもこっちのほうが明らかに楽でしたね。
まあそれでもけっこう時間がかかりましたが…
あれこれ書いたものの、結局は単純に実装力が足りなさそう。もっとコードを書くべし。
追記
コード量を削減しました。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = List(h) {
readLine()!!
}
val target = "snuke"
val dx = arrayOf(-1, 0, 1, -1, 1, -1, 0, 1)
val dy = arrayOf(-1, -1, -1, 0, 0, 1, 1, 1)
for (i in s.indices) {
for(j in 0 until w) {
if(s[i][j] == 's') {
for(k in 0 until 8) {
val ans = check(h, w, j, i, dx[k], dy[k], target, s)
if(ans.isNotEmpty()) {
ans.println()
return
}
}
}
}
}
}
fun check(h: Int, w: Int, x: Int, y: Int, dx: Int, dy: Int, target: String, s: List<String>)
: MutableList<Pair<Int, Int>> {
val ans = mutableListOf<Pair<Int , Int>>()
var xx = x
var yy = y
var count = 0
repeat(5) {
if(xx < 0 || xx >=w || yy < 0 || yy >=h) {
return@repeat
}
if(s[yy][xx] != target[count]) {
return@repeat
}
ans.add(yy + 1 to xx + 1)
xx += dx
yy += dy
count++
}
if(ans.size == 5) {
return ans
}
return mutableListOf()
}
fun MutableList<Pair<Int, Int>>.println() {
this.forEach {
println("${it.first} ${it.second}")
}
}
※消し忘れコメントは上のでは消しました
（執筆時間: 56分43秒）
Discussion