AtCoder Beginner Contest 329参加記（A～D）
Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）に参加したので記録を残します。
今回は4完です。
A - Spread
joinToString(" ") を使うといい感じでできます。
fun main() {
val s = readln()
println(s.toList().joinToString(" "))
}
B - Next
重複を排除した上で、2番目に大きい値が答えです。その通り重複除外して降順ソートして2番目の値を出力です。
（先にソートしてましたが、動作上はどちらでもいい）
fun main() {
val n = readln().toInt()
val a = readln().split(" ").map { it.toInt() }
println(a.sortedDescending().distinct()[1])
}
重複排除の時点で要素数が1つになってしまったらREとなってしまいますが、要素数は2以上で、全て同じであることはないという制約なので問題ないことをチラリと確認してから提出しました。えらい。
C - Count xxx
ランレングス圧縮すればいいと、すっと気づくことができました。1種類の文字のみからなる部分文字列の数は、要するに同じ文字が連続で並んでいる個数を文字ごとに求めて、それを合計すればいいということになります。ランレングス圧縮するとまさにその値を求めることができます。
ただし、同じ文字列を重複して数えることはできないので、一つの文字について個数が最大のものだけを採用して合計値を求めます。
ランレングス圧縮しなくても求められるかもしれませんが、私の場合はランレングス圧縮する関数を既に持っていたのでそれを貼って使うことで実装時間を短縮できました。
import kotlin.math.max
fun main() {
val n = readln().toInt()
val s = readln()
val e = rle(s)
val map = mutableMapOf<Char, Int>()
for((ch, count) in e) {
map[ch] = max(map.getOrDefault(ch, 0), count)
}
println(map.map { it.value.toLong() }.sum())
}
fun rle(s: String): List<Pair<Char, Int>> {
val ret = mutableListOf<Pair<Char, Int>>()
var c = s[0]
var count = 1
if(s.length == 1) {
ret.add(c to count)
}
for(i in 1 until s.length) {
if(c == s[i]) {
count++
} else {
ret.add(c to count)
c = s[i]
count = 1
}
if(i == s.length - 1) {
ret.add(c to count)
}
}
return ret
}
D - Election Quick Report
開票ごとに該当候補の得票数を増やして、その時点での当選者を出力していくだけなので考え方としては難しくありません。実装はちょっと面倒かも。得票数が同じなら番号が小さい方が当選というのがちょっと面倒。
その時点での当選者の更新はTreeSetに任せれば楽なのでそうしました。得票数が同じ場合に小さい方が大きいと判断させるために thenByDescending を使っています。この子、たまに役に立ちますね。
ただTreeSetにやらせるには、番号さえ一致していれば同一要素で、投票数を無視させる必要があります。そのため、そうなるように equals() と hashCode() を書き換えています。非常にお行儀が悪いのですが、まあ競プロなので許して…
ちなみに試してはいないですが、Candidateを可変にして使いまわしたらうまくいかないと思います。Candidateに直接加えても、TreeSetはそれに気づかないでしょうし。
import java.io.PrintWriter
import java.util.TreeMap
import java.util.TreeSet
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val out = PrintWriter(System.out)
val comparator = compareBy<Candidate> { it.count }.thenByDescending { it.num }
val map = mutableMapOf<Int, Candidate>()
val treeSet = TreeSet<Candidate>(comparator)
for(num in a) {
val current = map.getOrDefault(num, Candidate(num, 0))
val c = Candidate(num, current.count + 1)
treeSet.add(c)
println(treeSet.last().num)
map[num] = c
}
out.flush()
}
data class Candidate(
val num: Int,
val count: Int,
) {
override fun equals(other: Any?): Boolean {
if(other !is Candidate) {
return false
}
return this.num == other.num
}
override fun hashCode(): Int {
return num
}
}
あとは出力行数が多いのでPrintWriterで高速化を… と思ったけど、どう見ても使わずに出力していますね……
1000ms以上かかったのでなんか実行遅くない？と思いましたが、そのせいでした。
E - Stamp
Dまで30分かからず終わったので5完チャンスかもと思ってE問題を見ていました。
感想
自分にしては早めに4完できたので、過去最高パフォで温まりです。Highest復帰も見えてきました。
そうなった理由はたまたま自分が比較的得意そうな問題が並んだからです。しかし、できれば安定して毎回これくらいの成績を出したいところなんですよね。
また、なぜ今回の問題が比較的得意そうだったのかといえば、過去に似たような問題を解いたことがあったからですね。ランレングス圧縮は実装を持っていたくらいなのでもちろんですし、DでTreeSetを使うという発想も、同じようなことを何度かしたことがあります。それとEが解けなかったのは、逆にそれと似たような問題を解いたことがなかったためです。
つまり、安定して高いパフォを出すためには結局「知っている」問題を増やすしかないのではと思いました。もちろん知っている問題であるかどうかを見抜く必要があるし、ちゃんと実装できる必要もあるので、ただ知っているというだけではダメなのですが、そもそも知らなければ安定して高速に通すのは無理かなあと。
なので、これからは知っている問題数を増やす、つまり知識を増やすことを重視してやっていこうかなあと思いました。
そのための方法としてはとにかく問題数をこなす（要するに早めに解説を見る方針として効率を上げる）か、もしくは本などの教材を使うかですが、実際にどうするかはまだ考え中です。
まあ何にせよこれからも取り組んでいきます。
（執筆時間: 42分13秒）
Discussion