AtCoder Beginner Contest 354参加記
パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354）に参加したので記録を残します。
今回は3完です。連敗は止まりました。
A - Exponential Plant
条件を満たすまで単純に2の乗数を足していく操作を実行しました。現実的な回数で処理が終わるのはわかっていたので試行回数は適当に十分大きくしました。
import kotlin.math.pow
fun main() {
val h = readln().toLong()
var l = 0L
for(i in 0 until Int.MAX_VALUE) {
if(l > h) {
println(i)
return
}
l += 2.0.pow(i.toDouble()).toLong()
}
}
B - AtCoder Janken 2
問題の内容通りに計算します。ユーザ名と割当番号をまとめて扱ってソートすればOKですね。
fun main() {
val n = readln().toInt()
val persons = List(n) {
val (s, c) = readln().split(" ")
s to c.toLong()
}
.sortedBy { it.first }
.mapIndexed { index, pair -> Person(pair.first, pair.second, index) }
val t = persons.map { it.c }.sum()
val ans = persons.filter { it.i.toLong() == t % n }.first().s
println(ans)
}
data class Person(
val s: String,
val c: Long,
val i: Int,
)
C - AtCoder Magics
全ての組み合わせを試すことはできないので、捨てるかどうかを個別に高速に判断する必要があります。
ひとまず、強さでソートすることを考えました。その上で先頭の要素を見ると、強さでは最弱なのが確実で、あとはコストがそれより小さいものが1つでもあればそのカードは捨てることになるとわかります。なので、それより小さいコストが存在するかどうかを高速に判断できれば解けます。
今回はコストをTreeSetで持ちました。判断が終わったカードの情報は消していくことで、その時に注目しているカードのコストがTreeSetの先頭にあるかどうかで判断ができます。（先頭にあれば捨てない）
import java.util.TreeSet
fun main() {
val n = readln().toInt()
val cards = List(n) {
val (a, c) = readln().split(" ").map { it.toLong() }
Card(a, c, it+1)
}
.sortedBy { it.a }
//val cs = cards.sortedBy { it.c }
//
//val pos = mutableMapOf<Long, Int>()
//for(i in cs.indices) {
// pos[cs[i].c] = i
//}
val ccs = TreeSet<Long>()
for(c in cards) {
ccs.add(c.c)
}
val ans = cards.toMutableSet()
for(c in cards) {
if(ccs.first() != c.c) {
ans.remove(c)
}
ccs.remove(c.c)
}
println(ans.size)
println(ans.sortedBy { it.i }.map { it.i }.joinToString(" "))
}
data class Card(
val a: Long,
val c: Long,
val i: Int,
)
D - AtCoder Wallpaper
わかる気がしませんでした。
E - Remove Pairs
ゲーム系の問題ですが、これ系については知識が皆無です。とりあえずコンテスト中に以下を眺めてしました。
まあ、それだけで解けるはずもなく。Grundy数を求めればいいのかなと思ってたけど、解説を見たらDPで解いているので違うのかな？それともGrundy数を高速に求めるためにDPが必要なのかな？よくわかっていませんが、何にしても手に負える問題じゃなかったですね。
感想
Cの配点が350点なので解けるか不安でしたが、とりあえず解けました。久々に緑パフォが出て連敗が止まりました。まだHighestをだいぶ下回ったままですが。
先週書いた通り、とりあえず毎日1問は解くことを再開していました。その成果なのか、たまたま問題セットに恵まれただけなのかはよくわかりませんけどね。
Eは全然解けないですが、NimとかGrundy数とはどういうものなのかなんとなく知る機会になったのでよかったです。コツコツと続けていけばいいことありそうですね、きっと。
（執筆時間: 18分9秒）
Discussion