🙆♀️
AtCoder Beginner Contest 373参加記
AtCoder Beginner Contest 373に参加したので記録を残します。
今回も3完です。
A - September
添字+1と文字列の長さが一致しているかどうかを調べます。
fun main() {
val s = List(12) {
it + 1 to readln()
}
println(s.filter { it.first == it.second.length }.size)
}
B - 1D Keyboard
普通にシミュレーションするだけなんですが、何気に変数が多くてちょっと手間取りました。
import kotlin.math.abs
fun main() {
val s = readln()
val m = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
var current = s.indexOf("A")
var ans = 0
for(i in 1 until 26) {
val c = m[i]
val index = s.indexOf(c)
ans += abs(current - index)
current = index
}
println(ans)
}
C - Max Ai+Bj
各数列の最大値同士を足すだけです。明らかにC問題の難易度ではない（簡単すぎる）ので、誤読していないかどうか何度も確認してしまいました。
実際、なぜこの問題がC問題に配置されたのか…
fun main() {
val n = readln().toInt()
val a = readln().split(" ").map { it.toLong() }
val b = readln().split(" ").map { it.toLong() }
println(a.max() + b.max())
}
D - Hidden Weights
未訪問の頂点に適当な値を設定すれば隣接する頂点の値も決まるので、順次それをやっていけばいいんじゃないかと思いつつ、本当にそれでいいか確信を持てず。ちょっと今回やる気もいまいちだったのでそのまま撤退しました。
実際にそういう感じでやればよかったようですが、単純にそれだけだと矛盾が生じる場合があります。入力されたグラフと逆方向の辺も追加する（重みの符号は反転する）ことで解決できるようです。賢すぎて自力で思いつけませんね…
連結とは限らないので、1から
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val weightMap = mutableMapOf<Edge, Long>()
val graph = List(n + 1) { mutableListOf<Long>() }
for(i in 0 until m) {
val (u, v, w) = readln().split(" ").map { it.toLong() }
weightMap[Edge(u, v)] = w
weightMap[Edge(v, u)] = -w
graph[u.toInt()].add(v)
graph[v.toInt()].add(u)
}
val map = mutableMapOf<Long, Long>()
for(i in 1L..n) {
if(i in map) {
continue
}
map[i] = 0
val queue = ArrayDeque<Long>()
queue.add(i)
while (queue.isNotEmpty()) {
val u = queue.removeFirst()
for(v in graph[u.toInt()]) {
if(v in map) {
continue
}
map[v] = weightMap[Edge(u, v)]!! + map[u]!!
queue.add(v)
}
}
}
val ans = (1..n).map { map[it.toLong()] }.joinToString(" ")
println(ans)
}
data class Edge(
val u: Long,
val v: Long,
)
感想
前回に引き続き、一度途切れた参加習慣を取り戻すためのお試し参加というテンションでした。明らかに力は落ちていて、Dの考察で疲労を感じてとっとと撤退してしまいました。当分はこんな感じですが、初心に帰って参加だけを目標としてまずは参加習慣を取り戻そうと思います。
Discussion