🦁
AtCoder Beginner Contest 375参加記
先週のことになりますが、パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）に参加したので記録を残します。
とても無様な結果になりました。
A - Seats
やるだけなのですが、間の席に人が座っていないという条件を見落として1ペナ。これはひどい。
fun main() {
val n = readln().toInt()
val s = readln()
var ans = 0
for(i in 0 until n) {
if(i + 2 >= n) {
continue
}
if(s[i] == '#' && s[i+2] == '#' && s[i+1] == '.') {
ans++
}
}
println(ans)
}
B - Traveling Takahashi Problem
距離を計算する関数を作って、あとはそれを使ってシミュレーションです。最後に原点に戻るのを忘れてて、最初は答えが合いませんでした。
import kotlin.math.sqrt
fun main() {
val n = readln().toInt()
val xy = List(n) {
val (x, y) = readln().split(" ").map { it.toLong() }
x to y
}
var ans = 0.0
var current = 0L to 0L
for((x, y) in xy) {
val (a, b) = current
val d = calc(a, b, x, y)
ans += d
current = x to y
}
val (a, b) = current
ans += calc(a, b, 0, 0)
println(ans)
}
fun calc(a: Long, b: Long, c: Long, d: Long): Double {
val diff1 = a - c
val diff2 = b - d
return sqrt((diff1 * diff1 + diff2 * diff2).toDouble())
}
C - Spiral Rotation
ちゃんと計算量を見積もれてなくて、ただ実装するだけの問題と思い込んでTLEを出しました。そもそも実装ミスで愚直実装が終わるまでも時間がかかりました。これはひどい。計算量を削る方法はわからなくて解けず。
D - ABA
ほぼAIに解いてもらいました。（問題文手打ち）
発想としては、最初と最後が決まればあとはその間の文字数を数えればその分の答えを得られます。それを全ての組み合わせについて調べる、となります。
各文字の位置リストを作って、2個所以上にあれば間の文字数を数えます。ただ、間の文字数を数えるのを愚直にやるとTLEになります。そこは累積和を使います。
そもそも着想自体をAIに教えてもらったのと、累積和を使った高速化もAIにやってもらいました。これはひどい。
fun main() {
val s = readln()
val positions = List(26) { mutableListOf<Int>() }
for ((index, c) in s.withIndex()) {
positions[c - 'A'].add(index + 1)
}
// println(positions)
var ans = 0L
for (pos in positions) {
val m = pos.size
if (m >= 2) {
val suffixSum = LongArray(m + 1)
// 累積和の計算
for (i in m - 1 downTo 0) {
suffixSum[i] = pos[i].toLong() + suffixSum[i + 1]
}
for (i in 0 until m - 1) {
val count = (m - i - 1).toLong()
val total = suffixSum[i + 1] - (pos[i].toLong() + 1) * count
ans += total
}
}
}
println(ans)
}
感想
AIはルールに抵触しない範囲で使用したので問題はないものの、やはり敗北感が強い…
Discussion