AtCoder Beginner Contest 326参加記（A～C）
パナソニックグループ プログラミングコンテスト2023（AtCoder Beginner Contest 326）に参加したので記録を残します。
今回も3完です。
A - 2UP3DOWN
愚直に場合分けしました。もっと賢い実装方法があるはずとは思いましたが思いつかず。
fun main() {
val (x, y) = readln().split(" ").map { it.toInt() }
if(x < y) {
if(y - x <= 2) {
println("Yes")
} else {
println("No")
}
} else {
if(x - y <= 3) {
println("Yes")
} else {
println("No")
}
}
}
こうすればもっと簡単だったようですね…
fun main() {
val (x, y) = readln().split(" ").map { it.toInt() }
if(y in (x-3..x+2)) {
println("Yes")
} else {
println("No")
}
}
B - 326-like Numbers
愚直に調べました。3桁であると決まっているので、999まで全部調べればOK。答えは必ず存在するということなので、小さいほうから調べて最初に見つかったのを出力して抜けるだけです。
fun main() {
val n = readln().toInt()
for(i in n until 1000) {
val list = i.toString().map { it.digitToInt() }
if(list[0] * list[1] == list[2]) {
println(i)
return
}
}
}
C - Peak
けっこう難しいと感じて詰まってしまいました。最初に考えたのは累積和ですが、単純に累積和を使うだけの方法なら値がない位置も0で埋めるとかする必要があります。しかし、それをやるには制約が大きすぎて無理そうでした。
けっこう考え込んでしまいましたが、最終的に二分探索を使った解法を思いつきます。各
（-1があるのは半開区間のため）
ただ一つ問題がありまして、それは一つの座標に複数のプレゼントが置いてある場合の考慮です。Kotlinの二分探索メソッドだと、同じ値が複数ある場合にはそれのうちどれの位置が返ってくるのかわかりません。なので、値が複数ある場合はそれのうちどれの値が返ってきたのか判別して補正する考慮が必要でした。
どれが返ってくるのか判別するために、整数そのままではなく、その整数と順番を保持するデータクラスを作ってそれに対して二分探索するようにしました。
大まかな手順として、まずはソートします。それから各座標に何個のプレゼントが置いてあるのか記録して、上記のデータクラスの配列を生成します。（同じ値があったら連番を振るだけ）
あとは各
import kotlin.math.max
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
.sorted().toIntArray()
val map = mutableMapOf<Int, Int>()
for(i in 0 until n) {
map[a[i]] = map.getOrDefault(a[i], 0) + 1
}
val indexedA = mutableListOf<IndexedInt>()
var before = -1
for(i in 0 until n) {
val index = if(a[i] == before) {
indexedA[i-1].index + 1
} else {
0
}
indexedA.add(IndexedInt(a[i], index))
before = a[i]
}
var ans = 0
for(i in 0 until n) {
val to = IndexedInt(a[i] + m - 1, 0)
val index = indexedA.binarySearch(to, compareBy { it.value })
ans = if(index >= 0) {
val count = map[to.value]!!
val gap = indexedA[index].index + 1
max(ans, index - i + 1 - gap + count)
} else {
val index2 = -(index + 1)
max(ans, index2 - i)
}
}
println(ans)
}
data class IndexedInt(
val value: Int,
var index: Int,
)
面倒な実装になりましたが、C++の場合はlower_boundとupper_bound、Pythonの場合はbisect_leftとbisect_rightを使えばサクッと求められるようでした。羨ましい…ｗ
Kotlinでもlower_bound相当のことはできると思っていたのですが、lower_boundのほうは複数の値があった場合はその最初の位置が返ると保証されているっぽいので、lower_boundの劣化版という感じになりますね…
lower_boundとupper_boundみたいなのも作っておこうかなあ。
あとは、尺取り法でも解けるみたいでした。公式解説のコードが非常に簡潔で驚いたのですが、それは尺取り法を使った解法のようでした。せっかくなので尺取り法も勉強しようと思います。
解説記事を読んで、雰囲気だけ掴んだのですが実装は少し慣れが必要そう。
追記
しゃくとり法で解き直しました。
考え方としては以下の記事を参考にしました。
左手、右手で考えるのはめちゃくちゃわかりやすい…
右手は進む一方で、戻ってまた数え直す動作がないということですね。
実装自体は解説コードに近いです。
左手を固定して右手を可能な限り伸ばし、
右手が
import kotlin.math.max
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
.sorted()
.plus(listOf(Int.MAX_VALUE))
var ans = 0
var r = 0
for(l in 0 until n) {
while (a[r] - a[l] < m) {
r++
}
ans = max(ans, r - l)
}
println(ans)
}
さらに追記
lower_boundとupper_boundを作ろうかなと書きましたが、実際には作らなくていいことに気づきました。
以前他の問題の解説をもとに作った二分探索実装があるのですが
これが一般的には「めぐる式二分探索」として知られており、また普通に使うとlower_boundと同じ動きをすることがわかりました。また、lower_boundがあればupper_boundの動きもできるということで…
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
.sorted()
var ans = 0
for(i in 0 until n) {
val x = a[i]
val xm = x + m
val index = binarySearch(i, n) {
a[it] >= xm
}
ans = max(ans, index - i)
}
println(ans)
}
fun binarySearch(minNg: Int, maxOk: Int, isOk: (Int) -> Boolean): Int {
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
}
めぐる式二分探索はお気持ちがわかっていないとコードから意図を読み取りにくいかなと思って、使いこなすにはもうちょっと慣れが必要そうです。
感想
レートとしては負けなのですがけっこう楽しめました。なんとかCが解けて少しホッとしていまい。緑とか目指すならホッとしている場合じゃないのですが、まあ現状は緑になれる実力ではないので仕方ないです。今回の問題のおかげでlower_boundとかupper_bound、尺取り法のお気持ちがよくわかりました。こういう小さな成長を積み上げていきたいところです。
（執筆時間: 36分18秒）
Discussion