AtCoder Beginner Contest 335参加記（A～D）
AtCoder Beginner Contest 335（Sponsored by Mynavi）に参加したので記録を残します。
今回は4完です。
A - 202<s>3</s>
dropLast()で末尾を消してから4を付け足して出力しました。Kotlinだと文字列と数値をそのまま文字列として結合できます。（Javaと同じ。でもこれが許容されない言語のほうが多いのかな…）
fun main() {
val s = readln()
println(s.dropLast(1) + 4)
}
B - Tetrahedral Number
制約が小さいので単純に3重ループで全探索します。
辞書順についてはあまり直感的にわかってないのですが、サンプルを見た感じだと普通に実装すれば自然とそうなるっぽかったのでそのまま提出。
fun main() {
val n = readln().toInt()
for(i in 0 .. n) {
for(j in 0 .. n) {
for(k in 0 .. n) {
if(i + j + k <= n) {
println("$i $j $k")
}
}
}
}
}
C - Loong Tracking
実際に移動をシミュレーションすると間に合わないですが、移動の際に値が変わるのは先頭と末尾だけで、それ以外は位置が変わるだけなのでなんとか差分だけ更新する方法はないかなと考えました。
それで、dequeで管理すればいいと気づきました。移動の際は先頭に頭の移動先を追加して末尾の要素を削除するだけで済みます。参照は、そのまま添字でアクセスすればいいです。以前はdequeのランダムアクセスは遅いと思い込んでいたのですが、少なくともC++のdequeはそうではなく速いというのと、KotlinのArrayDequeも同様に速いということを最近知ったので、おかげで思いつくことができました。
import java.io.PrintWriter
fun main() {
val (n, q) = readln().split(" ").map { it.toInt() }
val br = System.`in`.bufferedReader()
val out = PrintWriter(System.out)
val deque = ArrayDeque<Pair<Int, Int>>()
for(i in 1..n) {
deque.add(i to 0)
}
for(i in 0 until q) {
val input = br.readLine().split(" ")
val type = input.first().toInt()
if(type == 1) {
val c = input.last()
val diff = when(c) {
"R" -> 1 to 0
"L" -> -1 to 0
"U" -> 0 to 1
"D" -> 0 to -1
else -> throw IllegalStateException()
}
val current = deque.first()
val new = current.first + diff.first to current.second + diff.second
deque.addFirst(new)
deque.removeLast()
} else {
val p = input.last().toInt()
val (x, y) = deque[p - 1]
out.println("$x $y")
}
}
out.flush()
}
なお、Pythonのdequeだとランダムアクセスが遅いらしく、コンテスト後にXを見ていて初めて知りました。リングバッファで実装されているか、線形リストで実装されているかで違うようです。
また、JavaのArrayDequeはそもそもランダムアクセス自体ができません。（メソッドがない）
言語アップデートが来る前はKotlinからJavaのArrayDequeを使っていたのですが、最近まで知りませんでした。
D - Loong and Takahashi
サンプルから、螺旋状に番号を振っていけばいいとわかりましたが実装が面倒そうでした。実はDFSとかで隣接するマスに番号を振っていくほうが実装が楽なのではと思って途中まで実装したのですが、真ん中をスルーする制御を入れたら微妙に破綻してサンプルも通らず。
仕方ないので、螺旋状に番号を振る方針に切り替えました。といっても自分で実装せずともググれば見つかるんじゃないかと思って、ググったらドンピシャなものを見つけたので拝借しました。最初からそうすればよかったのでは…
fun main() {
val n = readln().toInt()
val ans = Array(n) { IntArray(n) { -1 } }
val num = n * n
var h = 0
var w = 0
var dh = 0
var dw = 1
var cnt = 1
while (cnt < num) {
ans[h][w] = cnt
cnt++
if (w + dw >= n || w + dw < 0 || h + dh >= n || h + dh < 0 || ans[h + dh][w + dw] != -1) {
val tmp = dh
dh = dw
dw = -tmp
}
h += dh
w += dw
}
for(i in 0 until n) {
for(j in 0 until n) {
if(ans[i][j] == -1) {
print('T')
} else {
print(ans[i][j])
}
if(j == n - 1) {
println()
} else {
print(' ')
}
}
}
}
真ん中のTだけは面倒なのでif文で対処しました。
E - Non-Decreasing Colorful Path
閉路があり得るので単純パスは何通りもありますが、それらを全探索だと間に合わなさそう。わからないので撤退しました。後日解説ACしようかと思います。
感想
Dを通すのが遅かったわりには緑パフォが出て良い成績になりました。今回も参加者が多かったから…？
レート的にはなぜか好調なんですがあまり成長している気はしないので、慢心せずにやっていきます。
しかしdequeのランダムアクセスの件など、精進の中で知った知識がコンテストで活きると嬉しいですね。ちょっと問題を解いてみて解説を見ただけだけど、無駄ではなかったのだと。そういう、ちょっとしたことを一つ知るだけでも役に立つ場合があるので、焦らず少しずつ知見を増やしていきたいですね。
（執筆時間: 35分4秒）
Discussion