AtCoder Beginner Contest 337参加記（A～D）
トヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337）に参加したので記録を残します。
今回は3完です。
A - Scoreboard
それぞれの合計を計算して比較します。
fun main() {
val n = readln().toInt()
val xy = List(n) {
val (x, y) = readln().split(" ").map { it.toInt() }
x to y
}
val a = xy.map { it.first }.sum()
val b = xy.map { it.second }.sum()
if(a == b) {
println("Draw")
} else if(a > b) {
println("Takahashi")
} else {
println("Aoki")
}
}
これに2分以上かかってしまったので、コンディションはいまいちだったようです。
B - Extended ABC
ランレングス圧縮して判定しました。空文字もOKというのを見落としたりとかあれこれして2ペナです…
サンプルが合ってないのに提出とかしていて、落ち着きがなかったですね。
fun main() {
val s = readln()
val rle = rle(s)
val str = rle.map { it.first }.joinToString("")
val list = listOf("ABC", "A", "B", "C", "AB", "BC", "AC")
if(str in list) {
println("Yes")
} else {
println("No")
}
}
fun rle(s: String): List<Pair<Char, Int>> {
val ret = mutableListOf<Pair<Char, Int>>()
var c = s[0]
var count = 1
if(s.length == 1) {
ret.add(c to count)
}
for(i in 1 until s.length) {
if(c == s[i]) {
count++
} else {
ret.add(c to count)
c = s[i]
count = 1
}
if(i == s.length - 1) {
ret.add(c to count)
}
}
return ret
}
普通に解くと状態遷移を考えないといけないので面倒な問題ではあるのですが、それにしても2ペナはないなあ。
ソートしても一致するか判定するとか、正規表現を使うとか、楽な方法がいくつかあったようです。たしかに…
C - Lining Up 2
Lining UpというB問題が以前あり、解けなくて爆死したのを思い出してギョッとしました。しかしこちらは解けました。
→「Light It Up」の間違いでした！勘違いでギョッとしました
ややこしいのでもっといい解法があるかもしれませんが、最初にこれが思いつきました。
fun main() {
val n = readln().toInt()
val a = readln().split(" ").map { it.toInt() }
val list = a.mapIndexed { index, i -> Person(index + 1, i) }.sortedBy { it.number }
val ans = mutableListOf<Int>()
ans.add(list.first().index)
val numbers = list.map { it.number }
for(i in 0 until n - 1) {
val target = ans.last()
val ret = numbers.binarySearch(target)
val p = list[ret].index
ans.add(p)
}
println(ans.joinToString(" "))
}
data class Person(
val index: Int,
val number: Int,
)
全体的に命名が良くないので読みづらいですね…
D - Cheating Gomoku Narabe
これは解けませんでした。とりあえず各行と各列ごとそれぞれの答えを求めて、そのうちの最小値が答えということでよさそう。それでBと同様にランレングス圧縮して、'.'と'o'とで連続する箇所ごとに考えて、その大きさが
ランレングス圧縮に引きづられてしまったのですが、実際には区間として考えればよかったようです。ある地点から始まる長さ
区間内のそれぞれの個数は累積和を用いれば高速に求められます。
import kotlin.math.min
fun main() {
val (h, w, k) = readln().split(" ").map { it.toInt() }
val s = List(h) {
readln()
}
// 横
val ans1 = solve(h, w, k, s)
// 縦
val transposedS = mutableListOf<String>()
for(j in 0 until w) {
val sb = StringBuilder(h)
for(i in 0 until h) {
sb.append(s[i][j])
}
transposedS.add(sb.toString())
}
val ans2 = solve(w, h, k, transposedS)
val ans = min(ans1, ans2)
if(ans != Int.MAX_VALUE) {
println(ans)
} else {
println(-1)
}
}
fun solve(h: Int, w: Int, k: Int, s: List<String>): Int {
var ans = Int.MAX_VALUE
for(i in 0 until h) {
val cx = IntArray(w + 1)
val cd = IntArray(w + 1)
for(j in 1 .. w) {
cx[j] = cx[j-1] + if(s[i][j-1] == 'x') 1 else 0
cd[j] = cd[j-1] + if(s[i][j-1] == '.') 1 else 0
}
for(start in 1 .. w) {
val end = start + k - 1
if(end > w) {
break
}
if(cx[end] - cx[start-1] == 0) {
ans = min(ans, cd[end] - cd[start-1])
}
}
}
return ans
}
これは解きたかった。
感想
Dが解けなかったのは残念でした。ぞれぞれの行と列ごとに考えるというところまでは合っていましたが、区間として捉えるということができなかったのが敗因です。累積和を使って区間内の個数を数える問題自体はいくつか解いたことがあったので。個別のテクニックを覚えても、そのうち何を使うのか見いだせないことにはどうしようもなく。そういうのを鍛えるにはまだまだ解いた問題数が少ないのですかねぇ。
あとは、Bの2ペナも残念ですね。サンプルが合ってないのに気づかず提出というのはあまりにも…
なんか気分が乗っていないというか、テンションが低いというか、コンテストに臨むにあたって望ましい精神状態が整っていないままコンテスト開始してしまうことがたまにあり、昨日もそんな感じでした。そういうことがないように調子を整えるのも実力のかと思いますが、そういう面でも実力不足ですね。しかし、そういうのはどうやって整えたらいいのやら。なんかルーチンでも作るべきなんですかね？
（執筆時間: 42分25秒）
Discussion