AtCoder Beginner Contest 274 A～Cのメモ
キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）に参加したので記録を書いておきます。
A - Batting Average
浮動小数点の割り算をして小数第三位まで出力します。こういうのは素直に標準ライブラリの機能に頼ります。
printfはJavaにもあり、Kotlinからも使えることは知っていたので使いました。
記法は忘れてたので慌ててググりましたが…
fun main() {
val (a, b) = readLine()!!.split(" ").map { it.toDouble() }
System.out.printf("%.3f\n", b / a)
}
そして問題をよく読んでいなくて、小数第四位は切り捨てではなく四捨五入となっていることにコンテスト終了後に気づきました…
たまたま上記のほうほうだと四捨五入されるようなので助かりましたが。ちょっと今後ミスりそうで怖いですね。
B - Line Sensor
問題文の通りに数える処理を実装すれば問題ないです。横ではなく縦に数えます。
最後は一括で結合して出力ではなく都度出力するほうがいいかもしれませんが、半角スペースの有無とかでバグりそうな予感がして怖かったのでやめました。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val cList = List(h) {
readLine()!!
}
val ans = mutableListOf<Int>()
for(i in 0 until w) {
var cnt = 0
for(j in 0 until h) {
if(cList[j][i] == '#') {
cnt++
}
}
ans.add(cnt)
}
println(ans.joinToString(" "))
}
C - Ameba
ちょっと問題文の読解に時間がかかりました。
なにげに生まれるアメーバの番号は1から連続するようになっていますね。最初はアメーバ1しかいませんので、最初に起こることは必ずアメーバ1が分裂してアメーバ2と3が生まれることです。
次は2か3のどちらかが分裂して4と5が生まれると。
これは1をルートとした綺麗な2分木になると気づきました。コンテスト中に書いた下手な図を貼っておきます。
この時、それぞれの数字についての高さが答えとなります。なのでこの木を探索すれば解けそうではあったのですが、なんか冗長な気がしました。
結局、この高さに相当する情報を数値ごとに保持すればいいことに気づいたのでその方針で解きました。
（それに気づくのに時間がかかりました…）
import java.io.PrintWriter
fun main() {
val n = readLine()!!.toInt()
val aList = listOf(0) + readLine()!!.split(" ").map { it.toInt() }
val map = mutableMapOf<Int, Int>()
map[1] = 0
for(i in 1 .. n) {
val a = aList[i]
map[i * 2] = map[a]!! + 1
map[i * 2 + 1] = map[a]!! + 1
}
val out = PrintWriter(System.out)
for(i in 1 .. (2 * n + 1)) {
out.println(map[i])
}
out.flush()
}
aListは1オリジンに補正しています。高さは必ず親の高さ+1なのでそれを単純に計算します。
制約に「観察記録は矛盾していない」とありますので、親の高さが取れないということはありません。
ただ、1の場合の高さを設定しておく必要はあります。この値は必ず0です。
なお、上記では数値ごとの高さを保持するのにMapを使っていますが、バケットを使ってもよかったかなとコンテスト後に思って試しました。
バケットは、数値とそれに対応する値のマッピングを配列を使って保持するテクニックです。
添字をキー、その場所に格納する値がバリューとなった連想配列のようなものです。
事前に十分な大きさの配列を確保しておくことで実現します。
バケットは（値がメモリ上で物理的に連続しているという意味での原始的な）配列を使いますので、値の設定や参照が
Map（ハッシュテーブル）も同じく
import java.io.PrintWriter
fun main() {
val n = readLine()!!.toInt()
val aList = listOf(0) + readLine()!!.split(" ").map { it.toInt() }
val bucket = IntArray(2 * n + 2)
bucket[1] = 0
for(i in 1 .. n) {
val a = aList[i]
bucket[i * 2] = bucket[a] + 1
bucket[i * 2 + 1] = bucket[a] + 1
}
val out = PrintWriter(System.out)
for(i in 1 .. (2 * n + 1)) {
out.println(bucket[i])
}
out.flush()
}
やはりこちらのほうが有意に速かったです。メモリ使用量も少ない。
自分で書いてたくせに実践していなかったという…
D - Robot Arms 2
Cを解いた時点でそれなりに時間があったので少し考えてみましたが、ちょっと無理そうだなあと思いました。
解説を見ても厳しそうだったのでそっ閉じしました。
Twitterでこれの簡易版みたいな問題があると教えてもらったので、挑戦して記事を書きたいと思います。
教訓
- A問題も問題文はちゃんと読みましょう
- 複雑なデータ構造を考える前にシンプルな解法がないか考えましょう
Discussion