AtCoder Beginner Contest 320参加記（A～D）
トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)に参加したので記録を残します。
コンテスト中にはA～Cを解いて、Dはコンテスト後に通しました。
A - Leyland Number
問題文の通り実装です。Kotlinの場合はpow()メソッドを使えます。レシーバの型がDoubleなので変換して呼び出して、計算後にLongにしています。
制約をちゃんと見ていなかったですが、別にIntでもいいですね。
import kotlin.math.pow
fun main() {
val (a, b) = readln().split(" ").map { it.toInt() }
println((a.toDouble().pow(b) + b.toDouble().pow(a)).toLong())
}
B - Longest Palindrome
全部試します。substring()はなかなか慣れなくていつも混乱します。半開区間なので、内側のループはi + 1から始めます。
reversed()で反転させた文字列を得られるので、それと比較して同じなら回文といえます。
import kotlin.math.max
fun main() {
val s = readln()
var ans = 0
for(i in s.indices) {
for(j in i + 1..s.length) {
val ss = s.substring(i ,j)
if(ss == ss.reversed()) {
ans = max(ans, j - i)
}
}
}
println(ans)
}
C - Slot Strategy 2 (Easy)
これも全部試して、最小だったものが答えでした。
1秒が最小単位の時間で、一つの時間で押せるのは最大一つ（押さなくてもいい）、押す順番は自由に選べる、押したボタンに対応するリールは止まるがそれ以外の止めてないやつは回り続ける、という感じ。
リールは環状で、最後まで行った次はまた最初の数字に戻るので、3つのリール内に一つでも共通の数字があれば目的は必ず達成できます。逆に、一つもなければ達成不可能です。
なのでまずは達成可能かどうかを判定しました。
達成可能であれば、後は全部調べます。押す順番は自由なので、1→2→3と止めるパターン、1→3→2と止めるパターン... など全9通り調べます。
それぞれについて、0秒目に止めた場合、1秒目に止めた場合... と調べますが、今回は1つ目に止めたリールで表示されている数字と同じもの（最初に出現するもの）を2つ目、3つ目について調べるという感じでやりました。
しかし、あるリールを止めても他のリールは回り続けるため、2つ目と3つ目については単純に先頭からの探索だとダメで、リールを止めた時間の次の時間に表示される位置から調べます。
まあ素直にそのように探索すればよかったのですが、今回はループカウンタ自体は0から始めるが、経過した時間の文を足した位置の情報と比較、みたいなややこしいことをしてしまいました。
import kotlin.math.min
fun main() {
val m = readln().toInt()
val sList = List(3) {
readln()
}
val set2 = sList[1].toSet()
val set3 = sList[2].toSet()
var possible = false
for(c in sList.first()) {
if(c in set2 && c in set3) {
possible = true
break
}
}
if(!possible) {
println(-1)
return
}
var ans = Int.MAX_VALUE
for(i in sList.indices) {
val s1 = sList[i]
val s2: String
val s3: String
when (i) {
0 -> {
s2 = sList[1]
s3 = sList[2]
}
1 -> {
s2 = sList[0]
s3 = sList[2]
}
else -> {
s2 = sList[0]
s3 = sList[1]
}
}
// 探索
var cur = Int.MAX_VALUE
for(t in s1.indices) {
val c = s1[t]
for(j in s2.indices) {
if(s2[(j + t + 1) % m] == c) {
for(k in s3.indices) {
val num = k + t + 1 + j + 1
if(s3[num % m] == c) {
cur = min(cur, num)
}
}
}
}
for(j in s3.indices) {
if(s3[(j + t + 1) % m] == c) {
for(k in s2.indices) {
val num = k + t + 1 + j + 1
if(s2[num % m] == c) {
cur = min(cur, num)
}
}
}
}
}
ans = min(ans, cur)
}
println(ans)
}
コピペがダサいのと、コピペ後の修正漏れ（片方だけ修正）によって1ペナ貰う始末でしたが、一応解けてよかったです。
D - Relative Position
コンテスト中は解けませんでした。実はこれも全探索が間に合うのではないかと考えて実装していましたが、TLEが2つ出てそれを取り除けず…
コンテスト中に考えたのは以下のような感じです。
それで考えたのは、位置が既にわかっているほうを元に調べればいいのではということでした。位置がわかっているものからの相対位置が入力されている人についてはそれによって位置を特定して、位置が特定できたらまたそれをもとに位置を知ることができる人の位置を特定して... を繰り返せば、答えは得られるだろうと。同じような探索を何度もすることになりますが、Mapを使って
まあコンテスト中は通せなかったのですが、コンテスト後にその方針のまま計算量を改善して突っ走ったら最終的には通すことができました。ペナを量産しましたのでコンテスト中にそれを通すのは結局無理だったでしょうけど、方針自体は間違っているとは言えなかったのですね。残念。
import java.io.PrintWriter
fun main() {
val br = System.`in`.bufferedReader()
val (n, m) = br.readLine().split(" ").map { it.toInt() }
val aMap = mutableMapOf<Int, MutableList<Person>>()
repeat(m) {
val (a, b, x, y) = br.readLine().split(" ").map { it.toInt() }
val xx = x.toLong()
val yy = y.toLong()
val p = Person(a, b, xx, yy)
aMap.putIfAbsent(p.a, mutableListOf())
aMap[p.a]?.add(p)
val rp = Person(b, a, -xx, -yy)
aMap.putIfAbsent(p.b, mutableListOf())
aMap[p.b]?.add(rp)
}
val ans = mutableMapOf<Int, Pair<Long, Long>>()
ans[1] = 0L to 0L
var beforeSize: Int
val list = mutableListOf<Int>()
list.add(1)
val queue = ArrayDeque<Int>()
do {
beforeSize = ans.size
for(ii in 0 until list.size) {
val i = list[ii]
queue.add(i)
while (queue.isNotEmpty()) {
val a = queue.removeFirst()
if(!aMap.containsKey(a)) {
continue
}
for(p in aMap[a]!!) {
if(ans.containsKey(p.b)) {
continue
}
if(ans.containsKey(p.a)) {
val knownA = ans[p.a]!!
ans[p.b] = knownA.first + p.x to knownA.second + p.y
list.add(p.b)
queue.add(p.b)
}
if(ans.containsKey(p.a)) {
continue
}
if(ans.containsKey(p.b)) {
val knownB = ans[p.b]!!
ans[p.a] = knownB.first + p.x to knownB.second + p.y
list.add(p.a)
queue.add(p.a)
}
}
}
}
} while (beforeSize != ans.size)
val out = PrintWriter(System.out)
for(i in 1..n) {
if(ans.containsKey(i)) {
val (x, y) = ans[i]!!
out.println("$x $y")
} else {
out.println("undecidable")
}
}
out.flush()
}
data class Person(val a: Int, val b: Int, var x: Long, var y: Long)
ansというMapに格納、それをansの件数が変わらなくなるまで繰り返すという強引な手法です。まさか通るとは…
通らなかった版だと
なお、グラフとみなしてBFSなりDFSなりして調べるのが想定解だったようです。そりゃそうか…
BFSで解いてみたのがこちら。
import java.io.PrintWriter
fun main() {
val br = System.`in`.bufferedReader()
val (n, m) = br.readLine().split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Person>() }
repeat(m) {
val (a, b, x, y) = br.readLine().split(" ").map { it.toInt() }
graph[a].add(Person(a, b, x.toLong(), y.toLong()))
graph[b].add(Person(b, a, -x.toLong(), -y.toLong()))
}
val ans = mutableMapOf<Int, Pair<Long, Long>>()
ans[1] = 0L to 0L
// BFS
val queue = ArrayDeque<Int>()
queue.add(1)
val seen = BooleanArray(n + 1)
seen[1] = true
while (queue.isNotEmpty()) {
val v = queue.removeFirst()
for(node in graph[v]) {
if(seen[node.b]) {
continue
}
val (fromX, fromY) = ans[v]!!
ans[node.b] = fromX + node.x to fromY + node.y
queue.add(node.b)
seen[node.b] = true
}
}
val out = PrintWriter(System.out)
for(i in 1..n) {
if(i in ans) {
val (x, y) = ans[i]!!
out.println("$x $y")
} else {
out.println("undecidable")
}
}
out.flush()
}
data class Person(val a: Int, val b: Int, val x: Long, val y: Long)
当初は頂点番号をもとに
Mapを集約して、Mapから値を取得するオーバーヘッドを減らしたら通りました。
今回は訪問済の頂点はそのまま探索済みフラグを設定するだけで特に解除とか考えなくてよく、実装も楽だし計算量としても問題ないのですが、まさかの定数倍でやられました。うーん、難しいのやら簡単なのやら。
感想
Cが比較的早めに解けて緑パフォが出たのでレート的には勝ちでした。Dは解けてもよかったはずの問題なので残念ですが、最近は精進できていないのでむしろよくCが解けたなあという感想でした。
ABCに出る気力がわかないくらい体調が良くない週が続いていましたが、そのあたりも改善してきました。しばらくはこんな感じでやっていきます。
Mapの定数倍はけっこう重いぞというのは覚えておきます。Kotlin（というかJVM言語）の場合はオートボクシングの問題もあるので、なおさら重いのでしょうね。悩ましい。
（執筆時間: 57分28秒）
Discussion