AtCoder Beginner Contest 342参加記
HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）に参加したので記録を残します。
今回は3完です。Dが解けなかったのは残念だけどCまで早めに解けたので成績としては悪くありません。
A - Yay!
配点がいつもより高いので若干ビビってましたが、特に難しくはありませんでした。
基本的な考え方としては、1つしかない文字を見つけてからそれの位置を求めます。
今回はとりあえず1文字目を取得してそれが1つしかなかったら目当ての文字、そうでなければその文字ではないを見つけてそれが目当ての文字、というようにやりました。
fun main() {
val s = readln()
val f = s.first()
val c = if(s.toList().count { it == f } == 1) {
f
} else {
s.toList().first { it != f }
}
println(s.indexOf(c) + 1)
}
B - Which is ahead?
fun main() {
val n = readln().toInt()
val p = readln().split(" ").map { it.toInt() }
val q = readln().toInt()
for(i in 0 until q) {
val (a, b) = readln().split(" ").map { it.toInt() }
val ai = p.indexOf(a)
val bi = p.indexOf(b)
if(ai < bi) {
println(a)
} else {
println(b)
}
}
}
C - Many Replacement
置き換えを全部試すと間に合わないです。最後の状態だけが欲しいので、各文字が「最終的に」何になるのかをMapで管理して、一文字ずつそれで置き換えた文字を出力するようにしました。
面倒なのは、あるクエリで置き換えられた後の文字をさらに別の文字に置き換えるクエリが来るケースです。入力例1がそれに相当しrをaにするクエリの後にaをrにするクエリが来ます。これをマージして、rはrに置き換えるという扱いにすればいいです。
また、rをaにするクエリの後にrをbにするクエリが来るみたいなケースも考えられますが、これは後のクエリは無視するのが正しいです。後者のクエリが来た時点でrは既にaになっているので、rをbにするという操作は発生し得ないです。
ただし、それらの間にaをrにするクエリがあれば別です。今回の実装だと、その場合は結果的にrをbにするクエリが採用される動きになります。
マージするためにMapの要素を線形探索しますが、要素数は最大でもアルファベットの種類数（26個）しかないので問題なし。
fun main() {
val n = readln().toInt()
val s = readln()
val q = readln().toInt()
val map = mutableMapOf<Char, Char>()
for(i in 0 until q) {
val (c, d) = readln().split(" ").map { it.toCharArray().first() }
val toList = map.toList()
toList.filter { it.second == c }.forEach {
map[it.first] = d
}
if(c !in map) {
map[c] = d
}
}
val sb = StringBuilder()
for(i in 0 until n) {
sb.append(map[s[i]] ?: s[i])
}
println(sb)
}
D - Square Pair
これは解けませんでした。
素因数分解してから、同じ素因数について2個ずつのペアを作れたら除外という操作をして、残った数をかけ合わせた数を求めて、その数が同じになるペア同士の積は平方数になるはずです。なので、「その数を掛けたら平方数になる数の個数」を求めて足していくと考えました。
ただ、これだと平方数同士の掛け算について考慮が漏れています。他にもあれこれ考慮が甘くてサンプル2も通らず。
後でupsolveしたいです。
感想
Dが解けなかったのは残念ですが、Cが自分基準だと早めに解けたのでなんとかなりました。
Dは解けなかったとはいえ方向性は間違ってない感じだったんですよね。最近は簡単な問題を埋めることしかできてないですが、それにしてはわりと善戦できている感じ。
あと+26で緑になるのですが、私は基本的に大勝ちしないので次回入緑戦かというと微妙なところです。あまり気負わずのんびりとやります。
（執筆時間: 29分18秒）
Discussion