AtCoder Beginner Contest 318参加記（A～C）
THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）に参加したので記録を残します。
今回も体調がヤバいので出るかどうか迷っているうちに開始時刻が来てしまいましたが、とりあえず少し遅れてUnratedで出ました。
A - Full Moon
私の頭では計算で求めるとかできないので、素直にループを回して数えました。
全体の日数が少なくて最初に満月が見られる日が来る前に終わってしまうケースは別途考慮しました。
fun main() {
val (n, m, p) = readln().split(" ").map { it.toInt() }
if(n < m) {
println(0)
return
}
var ans = 1
for(i in (m + 1)..n) {
if((i - m) % p == 0) {
ans++
}
}
println(ans)
}
B - Overlapping sheets
面積を計算して足すだけかと最初思いましたが、重なっている部分を引く必要がありました。
しかし、重なっている部分の面積を求めるとかだと面倒です。結局グリッドを作って埋めていって、埋まった数を数える実装としました。既に埋まっている部分を再度埋めても特に問題ないので、重なっているかどうかを考えなくて済みます。
fun main() {
val n = readln().toInt()
val grid = List(100) { BooleanArray(100) }
for(z in 0 until n) {
val (a, b, c, d) = readln().split(" ").map { it.toInt() }
for(i in a until b) {
for(j in c until d) {
grid[i][j] = true
}
}
}
println(grid.flatMap { it.toList() }.count { it })
}
C - Blue Spring
頭動かないのでABで撤退かなと思いましたが、Cはそんなに難しくなさそうだったのでやってみました。
パスを全く使わない場合の合計金額は単純に全部足せば求められますが、パスを何セットか買うことでそれより安く済ませられるかもしれません。それで何セット買うと最小になるかという問題ですね。
パスの購入回数に明示的な上限はないですが、全日程をカバーする分だけ買ったらそれより多く買うメリットが全くないので、実質的には上限があります。それを全部調べれば求められます。探索範囲が最大になるのは
パスを買った場合は、パスの代金はかかるかわりにいずれかの日の料金をタダにできると捉えます。金額を最小にするためには通常料金が高い日を優先してタダにする必要がありますので、運賃のリストを降順ソートして高いほうからパスの枚数分をタダにしてから合計値を求めて、それにパスの購入代金を足す、を各パターンごとに計算します。
合計値を求めるのに時間がかかったら意味ないので、そこは累積和で高速に求められるようにしました。
import kotlin.math.min
fun main() {
val (n, d, _p) = readln().split(" ").map { it.toInt() }
val f = readln().split(" ").map { it.toLong() }
.sortedDescending()
val p = _p.toLong()
val s = LongArray(n + 1)
for(i in 0 until n) {
s[i+1] = s[i] + f[i]
}
val diff = if(n % d == 0) 0 else 1
var ans = (n / d) * p + (diff * p)
for((count, i) in (0 until n step d).withIndex()) {
ans = min(ans, s[n] - s[i] + p * count)
}
println(ans)
}
ans の初期値は全ての日についてパスを使った場合です。下で書いているfor文の条件だとそれが抜ける可能性があるので。
感想
3完といっても1時間近くかかってしまうなど万全とは言えない感じで、本当はRatedにしたかったけどUnratedにしたのは妥当という感じでした。
まあしょうがないので、可能ならRatedでダメならUnratedでもいいのでとりあえず参加する、という感じでやっていきます。
体調改善のための取り組みも一応あれこれやっているので、今後に期待です。
体調の他にも精進が止まっているという問題もあるのですが、それは他のことを勉強するためです。勉強しつつ精進も、というのは今の体調だと耐えられないことが経験上わかっているので、これもしょうがないですね…
一区切りついたら精進を再開したいですが、進捗が悪くていつ終わるのやらという感じになっています。レート変動がないまま今年が終わってしまいそうですね…
（執筆時間: 29分4秒）
Discussion