AtCoder Beginner Contest 374参加記
キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）に参加したので記録を残します。
テンション低かったのですが、4完までいけました。
A - Takahashi san 2
endsWith()で判定できます。
fun main() {
val s = readln()
if(s.endsWith("san")) {
println("Yes")
} else {
println("No")
}
}
B - Unvarnished Report
考えないといけないケースを減らそうと思って早期リターンを入れたのですが、場合分けが増えてかえって面倒になった気が…
文字数が異なる、かつ文字の差分があるパターンを危うく見落とすところでした。
import kotlin.math.max
import kotlin.math.min
fun main() {
val s = readln()
val t = readln()
if(s == t) {
println(0)
return
}
val j = min(s.length, t.length)
for(i in 0 until j) {
if(s[i] != t[i]) {
println(i + 1)
return
}
}
if(s.length != t.length) {
if(s.length > t.length) {
println(t.length + 1)
} else {
println(s.length + 1)
}
return
}
}
C - Separated Lunch
制約が小さいので全部試せばよさそうだと思いました。bit全探索を使って片方のグループに割り当てる部署を決めてその合計値を求めて、それを全体の合計から引くことでもう片方のグループの人数を求めて比較しました。
import kotlin.math.max
import kotlin.math.min
fun main() {
val n = readln().toInt()
val k = readln().split(" ").map { it.toLong() }
val total = k.sum()
var ans = Long.MAX_VALUE
bitmask(n) { bits ->
if (bits.all { false }) {
return@bitmask
}
var sum = 0L
for(i in 0 until n) {
if(bits[i]) {
sum += k[i]
}
}
val tmpAns = max(sum, total - sum)
ans = min(ans, tmpAns)
}
println(ans)
}
fun bitmask(n: Int, action: (List<Boolean>) -> Unit) {
val limit = 1 shl n
for(i in 0 until limit) {
val bits = i.toString(2).padStart(n, '0')
action(bits.map { it == '1' })
}
}
if (bits.all { false }) {
return@bitmask
}
これは別にいらなかったかも。グループの配分としてはありえないけどそれが最小になることはないし。全部trueになるパターンは見落としてるけど、それも最小になることはないので助かった。。。
D - Laser Marking
これも制約が小さいので、順列全列挙で全部試せばいいと思いました。順列全列挙で印字する順番を決めます。ただ、各線分についてどちらを始点とするかも考えないといけないと気づく。どうしようか迷いましたが、これも制約が小さいことから全部試しても
コンテスト中は感覚的にいけると思っただけで実際に何通りになるかの計算まではしなかったです。最大で
私は数学ができませんので線分の長さの求め方を忘れていてググりましたし、なんなら算数もできませんので速さと距離から時間を求める式も忘れていてググりました。
import kotlin.math.min
import kotlin.math.sqrt
fun main() {
val (n, s, t) = readln().split(" ").map { it.toInt() }
val list = List(n) {
val (a, b, c, d) = readln().split(" ").map { it.toInt() }
Point(a, b) to Point(c, d)
}
var ans = Double.MAX_VALUE
val mlist = (0 until n).toMutableList()
val permutation = Permutation(mlist)
bitmask(n) { bits ->
//println(bits)
permutation.forEach { p ->
var currentPoint = Point(0, 0)
var time = 0.0
//println(p)
for(i in p) {
val point1 = list[i].first
val point2 = list[i].second
// 開始地点までの移動の時間
var start = currentPoint
var end = if(!bits[i]) {
point1
} else {
point2
}
time += calcTime(start, end, s)
currentPoint = end
// レーザー照射の時間
start = end
end = if(!bits[i]) {
point2
} else {
point1
}
time += calcTime(start, end, t)
currentPoint = end
//println(time)
}
ans = min(ans, time)
}
}
println(ans)
}
fun calcTime(point1: Point, point2: Point, speed: Int): Double {
val x1 = point1.x
val y1 = point1.y
val x2 = point2.x
val y2 = point2.y
val diffX = x2 - x1
val diffY = y2 - y1
val dist = sqrt((diffX * diffX + diffY * diffY).toDouble())
return dist / speed
}
data class Point(
val x: Int,
val y: Int,
)
class Permutation<T>(private val list: MutableList<T>) {
private val queue = ArrayDeque(list)
fun forEach(action: (MutableList<T>) -> Unit) {
forEach(0 ,0, action)
}
fun toList(): List<List<T>> {
val list = mutableListOf<List<T>>()
forEach {
list.add(it.toList())
}
return list.toList()
}
private fun forEach(count: Int, layer: Int, action: (MutableList<T>) -> Unit) {
if(count == list.size) {
action(list)
return
}
for(i in count until list.size) {
val elem = queue.removeFirst()
list[layer] = elem
forEach(count + 1, layer + 1, action)
queue.add(elem)
}
}
}
fun bitmask(n: Int, action: (List<Boolean>) -> Unit) {
val limit = 1 shl n
for(i in 0 until limit) {
val bits = i.toString(2).padStart(n, '0')
action(bits.map { it == '1' })
}
}
重実装ってほどではないですが、ちょっと大変でしたね。 time += が time = になってて結果が合わないとかして混乱してました。
感想
レート捨てるつもりで参加しているのですが、謎に上がっています。今回はDまではどれも全探索でしたからね、考察は難しくなくて実装力勝負の感じでした。実装力を鍛えたくて競プロやっているので、こういう回を落とさずに済んだのは嬉しいところです。しばらく参加してなくてブランクがありますが、実装力はそんなに落ちていなくて少し安心。ただ、おそらく考察力は死んでるので今回のような結果は再現性がなく、ちょっと考察が必要なC問題とか来たら爆死する可能性があります。まあ、最初に書いた通りレートは捨ててもいいと思っているのでそれはそれでいいのですが…
今回はRated登録前はテンションが低くて参加を見送るか迷ったので、まだ参加習慣を取り戻せているかは怪しいところ。来週以降も参加できるようにしたいですね。
（執筆時間: 20分50秒）
Discussion