AtCoder Beginner Contest 330参加記（A～E）
トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)に参加したので記録を残します。
今回は4完です。Eはコンテスト後に解いたものです。
A - Counting Passes
オーソドックスなA問題ですね。filterして残った件数が答えです。
fun main() {
val (n, l) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
println(a.filter { it >= l }.size)
}
B - Minimize Abs 1
オーソドックスなB問題… じゃなかったですね。まず問題文がけっこう難しくて読み取るのに時間がかかりました。さらに、問題文の意味がようやくわかっても、今度は明らかに全探索だと無理な制約であることに気づきます。
あれこれ考えて、要するに
それなら場合分けすればよさそう。あとは
import kotlin.math.abs
import kotlin.math.absoluteValue
fun main() {
val (n, l, r) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val ans = mutableListOf<Int>()
for(i in 0 until n) {
if(a[i] in l..r) {
ans.add(a[i])
} else if(a[i] < l) {
ans.add(l)
} else {
ans.add(r)
}
}
println(ans.joinToString(" "))
}
fun binarySearch(minNg: Long, maxOk: Long, isOk: (Long) -> Boolean): Long {
var ng = minNg
var ok = maxOk
while(abs(ok - ng) > 1) {
val mid = (ok + ng) / 2
if(isOk(mid)) {
ok = mid
} else {
ng = mid
}
}
return ok
}
試行錯誤の途中で混入したいらないコードが入っていますが…
ここまでで19分くらい費やしてしまいました。
C - Minimize Abs 2
Bと違ってすごくシンプルな問題文です。しかしこういう問題のほうがけっこう難しかったりしがちなイメージ…
まずは全探索を考えましたが、
import kotlin.math.abs
import kotlin.math.absoluteValue
import kotlin.math.min
fun main() {
val d = readln().toLong()
val ans = solve(d)
println(ans)
}
fun solve(d: Long): Long {
val limit = 5000000L
val list = (1L..limit).map { it * it }
var ans = Long.MAX_VALUE
for(x in 0L..limit) {
val x2 = x * x
val diff = x2 - d
if(diff >= 0) {
ans = min(ans, diff)
} else {
val absDiff = abs(diff)
val tmpIndex = list.binarySearch(absDiff)
if(tmpIndex >= 0) {
return 0L
} else {
val index = -(tmpIndex + 1)
val beforeDiff = if(index - 1 >= 0) {
(list[index-1] - absDiff).absoluteValue
} else {
Long.MAX_VALUE
}
val afterDiff = if(index < list.size) {
(list[index] - absDiff).absoluteValue
} else {
Long.MAX_VALUE
}
val minDiff = min(beforeDiff, afterDiff)
ans = min(ans, minDiff)
}
}
}
return ans
}
最初は1000000Lまで探索するコードを投げてWAを出しました。愚直回との照合とかしてもなかなかダメなケースを見つけられず、もしかしたらと思って雑に5000000Lに増やして投げたら通ったという…
まだまだです。
D - Counting Ls
Cを解いた時点でもう時間が残り少なくて、Dは無理かと思っていましたが一応考えてみました。
まず、全マスを全探索するのは問題ないことを確認。それで、求めるとしたら各マスごとの値を求めて合計値を出せばよさそうかなと。各マス（oであるマス）一つ一つに注目すると、それと同じ行に（そのマスも含めて）2以上oがあり、かつ同じ列にも（そのマスも含めて）2以上oがあれば条件を満たします。それぞれちょうど2つの場合が最低条件で、その場合のそのマスに対する答えは1ですね。じゃあoが2より大きい場合はどうなるのか？と考えると、1増えるたびに掛け合わせで増えていくことが想像できました。3マスのうち1マスでも異なれば区別するわけなので。
じゃあ掛け算してそれの合計値を求めたらそれっぽいよねーと思ってその通りコードを書いてみたらなんとサンプルが合う。も、もしかしてと提出してみたら通りました。やったぜ。
fun main() {
val n = readln().toInt()
val s = List(n) {
readln()
}
val hCount = IntArray(n)
val vCount = IntArray(n)
for(i in 0 until n) {
for(j in 0 until n) {
if(s[i][j] == 'o') {
hCount[i]++
vCount[j]++
}
}
}
var ans = 0L
for(i in 0 until n) {
for(j in 0 until n) {
if(s[i][j] == 'o' && hCount[i] >= 2 && vCount[j] >= 2) {
ans += hCount[i].minus(1) * vCount[j].minus(1)
}
}
}
println(ans)
}
E - Mex and Update
Dを解いた時点でもう10分も残ってなかったのでさすがにEは無理でしたが、しかし見た感じ頑張ればいけそうな感触を得ました。なのでコンテスト後に解説は見ずにやってみました。1ペナ出しましたが解けたので、Cで時間を溶かさなければいけた可能性が…
基本的に、クエリで指定された通りの操作を実際にやればいいように思いました。最初の時点の答えは事前に調べておけばわかるので、あとは入力に合わせて答えを更新するかどうかを考えていけばいいのかなと。具体的には、クエリごとに
いちいち答えを探したらもちろん間に合わないので、答えとしてあり得る値を全部事前に調べておけばいいと思いました。TreeSetで管理して、都度最小値を出せばよさそうと。ただ、TreeSetだと重複を管理できないので、個数を管理するMapを別途作りました。
import java.io.PrintWriter
fun main() {
val (n, q) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }.toMutableList()
val aSet = a.toSet()
val mexCandidates = sortedSetOf<Int>()
val counts = mutableMapOf<Int, Int>()
for(i in 0..2 * 100000 + 1) {
if(i !in aSet) {
mexCandidates.add(i)
}
}
a.forEach {
counts[it] = counts.getOrDefault(it, 0) + 1
}
val br = System.`in`.bufferedReader()
val out = PrintWriter(System.out)
repeat(q) {
val (i, k) = br.readLine().split(" ").map { it.toInt() }
val current = a[i-1]
counts[current] = counts[current]!! - 1
counts[k] = counts.getOrDefault(k, 0) + 1
if(counts[current] == 0) {
mexCandidates.add(current)
}
if(counts[k] == 1) {
mexCandidates.remove(k)
}
a[i-1] = k
out.println(mexCandidates.first())
}
out.close()
}
よく見たら、kじゃなくてxが正しいですね… まあいいか。
TreeSetは各操作を
あ…… うん
感想
BCで詰まったけどやっぱり解けると楽しい！レート的にも、半年ぶりにHighestを更新できてよかったです。ただ、現状は知識がおそらく偏っているので安定してこのような結果はなかなか出せないんですよね。ムラがある。
レート的にもそうですが、そもそも解けないと楽しくないというのもあり…
と考えると、知識が偏っていると解けるかどうか運に大きく左右されるのでやはりよくないなと思いました。だいたいどんな分野の問題でも、少なくともCまでなら確実に解けるようにしたいですね。それも高速に解きたい。時間が多く残れば上位の問題も解ける可能性が出てきますし、解けなくても解けないなりに考察しておけばupsolveもしやすくなりますし。
ということで、満遍なく知識を得られるように鉄則本を読んでいます。まだ最初のほうなので前回、今回が好調だったのは偶然です。効果が出るとしたらもっと先ですね。効果が出るといいなあ…
（執筆時間: 1時間6分37秒）
Discussion