AtCoder Beginner Contest 308参加記（A～D）
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)に参加したので記録を書きます。
今回は3完です。Dはコンテスト後に引き続き挑戦しましたが通らず。とりあえず今TLEになるコードを載せておきます。
2ペナで、Cが通ったのも遅いので微妙な順位に。ただ、最近爆死が続いてレーティングが下降していたので、今回のような成績でも下がりはしませんでした。
A - New Scheme
ソートしても順番が変わらないかどうか、条件を満たさない要素を除外しても件数がかわらないかどうか、を調べました。
fun main() {
val s = readLine()!!.split(" ").map { it.toInt() }
if(s == s.sorted() && s.filter { it in 1..675 }.size == s.size
&& s.filter { it % 25 == 0 }.size == s.size) {
println("Yes")
} else {
println("No")
}
}
B - Default Price
全探索でも大丈夫だよなと制約をチラ見しつつ、問題文の通りのことを調べました。文字が多くて若干もたつきました。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val c = readLine()!!.split(" ")
val d = readLine()!!.split(" ")
val p = readLine()!!.split(" ").map { it.toInt() }
var ans = 0L
for(i in c.indices) {
val index = d.indexOf(c[i])
if(index < 0) {
ans += p.first()
} else {
ans += p[index + 1]
}
}
println(ans)
}
C - Standings
最初は単純に実装しました。確率を扱う際に浮動小数点を使うことになるのが気になるけど、まあたぶん大丈夫でしょうと高を括って提出。
Kotlinでのソートの第二条件の指定方法などを慌てて調べました。
fun main() {
val n = readLine()!!.toInt()
val ab = List(n) {
readLine()!!.split(" ").map { it.toInt() }
}
val list = mutableListOf<Pair<Int, Double>>()
for(i in ab.indices) {
val (a, b) = ab[i]
val p = a.toDouble() / (a + b)
list.add(i + 1 to p)
}
println(list.sortedWith(compareByDescending<Pair<Int, Double>>({ it.second }).thenBy({ it.first })).map { it.first }.joinToString(" "))
}
ダメか…
一応、オーバーフローやメモリ不足（最後でかいStringを作っているので）の可能性も考えてみましたが、それらの問題はなさそうに思えて、やはり誤差かーと思いました。
それからBigDecimalを使おうとしたりあれこれしましたがうまくいかず。
最終的には以下の実装でACとなりました。
fun main() {
val n = readLine()!!.toInt()
val ab = List(n) {
readLine()!!.split(" ").map { it.toInt() }
}
val list = mutableListOf<Pair<Int, Pair<Long, Long>>>()
for(i in ab.indices) {
val (a, b) = ab[i]
list.add(i + 1 to (a.toLong() to (a + b).toLong()))
}
val comparator = Comparator<Pair<Int, Pair<Long, Long>>>{ a, b ->
if(a.second.first * b.second.second == b.second.first * a.second.second) {
0
} else {
if(a.second.first * b.second.second < b.second.first * a.second.second) 1 else -1
}
}.thenBy { it.first }
println(list.sortedWith(comparator).map { it.first }.joinToString(" "))
}
浮動小数点を使わず、分数と見立てて比較しました。Pairがネストしているので読みづらいですね…
Pairをネストさせることで人の番号、確率（分子、分母）の情報を保持して比較用のComparatorを作ってsortWith()に渡しました。
ここでかなり時間がかかりました。
D - Snuke Maze
解けなかった問題です。Maze（迷路）という単語の時点で嫌な予感しかしないってやつです。
各マスを頂点、隣接を辺と見立てたグラフとして扱えて、それで探索すればいいというのはすぐにわかりましたが、実装が間に合いませんでした。
まあコンテスト後に提出してもTLE祭りで未だに通っていないので、どのみち時間内に通すのは無理だったようですが。
とりあえず直近の提出（TLE）を載せておきます。
var graph = mutableMapOf<Pair<Int, Int>, MutableList<Pair<Int, Int>>>()
var s = listOf<CharArray>()
fun main() {
Thread(
null,
{
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
s = List(h) {
readLine()!!.toCharArray()
}
if(s[0][0] != 's') {
println("No")
return@Thread
}
graph = mutableMapOf()
for(i in 1..h) {
for(j in 1..w) {
graph.putIfAbsent(i to j, mutableListOf())
graph.putIfAbsent(i-1 to j, mutableListOf())
graph.putIfAbsent(i+ 1 to j, mutableListOf())
graph.putIfAbsent(i to j-1, mutableListOf())
graph.putIfAbsent(i to j+1, mutableListOf())
if(i != 1) {
graph[i to j]!!.add(i-1 to j)
}
if(i != h) {
graph[i to j]!!.add(i+ 1 to j)
}
if(j != 1) {
graph[i to j]!!.add(i to j-1)
}
if(j != w) {
graph[i to j]!!.add(i to j+1)
}
}
}
if(dfs(1 to 1, h, w)) {
println("Yes")
} else {
println("No")
}
},
"",
128 * 1024 * 1024
).start()
}
val seen = mutableSetOf<Pair<Int, Int>>()
val nextMap = mapOf('s' to 'n', 'n' to 'u', 'u' to 'k', 'k' to 'e', 'e' to 's')
fun dfs(p: Pair<Int, Int>, h: Int, w: Int): Boolean {
if(p.first == h && p.second == w) {
return true
}
seen.add(p)
val next = nextMap[s[p.first - 1][p.second - 1]]
for(node in graph[p]!!) {
if(node in seen) {
continue
}
if(next == null || next != s[node.first - 1][node.second - 1]) {
continue
}
if(dfs(node, h, w)) {
return true
}
}
return false
}
必要な探索以外していないと思っているのですが、なぜTLEになるのかわからず。今日のところは諦めて後日見てみます。
追記
以下のコードで通りました。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val s = Array(h) {
readLine()!!
}
if (s[0][0] != 's') {
println("No")
return
}
val seen = Array(h) { BooleanArray(w) }
seen[0][0] = true
val nextMap = mapOf('s' to 'n', 'n' to 'u', 'u' to 'k', 'k' to 'e', 'e' to 's')
val di = arrayOf(0, 0, 1, -1)
val dj = arrayOf(1, -1, 0, 0)
val queue = java.util.ArrayDeque<Pair<Int, Int>>()
queue.addLast(0 to 0)
while (queue.isNotEmpty()) {
val v = queue.removeFirst()
val next = nextMap[s[v.first][v.second]]
for(k in 0 until 4) {
val i = v.first + di[k]
val j = v.second + dj[k]
if(i !in 0 until h || j !in 0 until w) {
continue
}
if(next == null || next != s[i][j]) {
continue
}
if(seen[i][j]) {
continue
}
seen[i][j] = true
queue.addLast(i to j)
}
}
if(seen[h-1][w-1]) {
println("Yes")
} else {
println("No")
}
}
グラフの作成処理が無駄だったのと、訪問先の頂点を全て探索済にする必要があったのが大きな違いです。再帰DFSをやめていますが、それはあまり関係ないです。
訪問先の頂点を全部探索済にしていい理由が最初はよくわからなかったのですが、訪問済にしてもその頂点と隣接する頂点を全部見ることには変わりがないからですね。
こういうミスをするということはグラフについて全然わかってないのかもしれません。
なお、再帰DFSのままかつ探索済のフラグ更新についてだけ修正した提出もしてみましたが、それでも1ケースだけTLEがとれませんでした。
グラフの作成処理については、無駄だったとはいえ計算量としては変わらない気がしたのですが、これをやめただけでめちゃくちゃ改善しました。
遅くないどころか、上に掲載したBFS解法より速いくらいですね…（誤差でしょうけど）
うーん、まだまだです。まだまだ過ぎる。
感想
あまり良い成績ではなく反省点も多々ありますが、最近不調なのでまあこんなものなのかなという気も。最終的には一応Cが通ってよかったです。
当面はとりあえずコンテストには出続けるということを意識したいと思います。
（執筆時間: 23分50秒）
Discussion