AtCoder Beginner Contest 323参加記（A～D）
ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)に参加したので記録を残します。
今回も3完です。Dはコンテスト後に通したものです。
A - Weak Beats
そのまま一文字ずつチェックしました。
fun main() {
val s = readln()
for(i in 0 until s.length) {
if((i+1) % 2 == 0 && s[i] != '0') {
println("No")
return
}
}
println("Yes")
}
以下のように書けば（見かけ上）ネストを一段減らせて実装も少し楽だったのですが、なぜかコンテスト中はすっと出てこなかったです。
fun main() {
val s = readln()
if(s.filterIndexed { index, c -> index % 2 == 1 }.all { it == '0' }) {
println("Yes")
} else {
println("No")
}
}
B - Round-Robin Tournament
表を見て各人の勝利数を数えて記録した後にソートします。勝利数が同じの場合の第二ソート条件が必要なのがちょっと面倒な感じ。というかその場合の書き方を覚えてなくて慌てて調べました。
Kotlinの場合はsortedWithにComparatorを渡せばよく、そのComparatorをサクッと作るためのメソッドもある、とかは覚えていました。
fun main() {
val n = readln().toInt()
val s = List(n) {
val s = readln()
s
}
val list = (1..n).map { Player(it, 0) }
for(i in 0 until n) {
for(j in 0 until n) {
if(s[i][j] == '-') {
continue
}
if(s[i][j] == 'o') {
list[i].win++
} else {
list[j].win++
}
}
}
val ans = list.sortedWith(compareByDescending<Player> { it.win }.thenBy { it.n })
println(ans.map { it.n }.joinToString(" "))
}
data class Player(
val n: Int,
var win: Int,
)
C - World Tour Finals
重実装ってほどではないですが実装ゲーでしたね。制約はちゃんと見て、愚直にやるだけで問題ないことを確認してから実装しました。
まずは各プレイヤーの現在の得点とその最大値を調べて記録します。あとは各プレイヤーの得点を見て、単独一位のプレイヤーの場合は0、それ以外のプレイヤーの場合は配点が高い問題を優先して解いていって数え上げて結果を出力です。既に解いている問題は再度解かないようにします。
最大の得点を持つプレイヤーが複数いるかもしれないのでその考慮を入れています。（最大の得点を先に調べて、その得点を持つプレイヤーが何人いるか調べるという力技）
ボーナス点があるので基本的には得点はかぶらなさそうですが、ボーナス点が100点のプレイヤーがいる場合はあり得そうで。
最後の問題を解くことでようやく最大得点を得るプレイヤーの場合に結果が出力されないというしょうもないバグのせいで1ペナもらいました。残念です・・・
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val s = List(n) {
val s = readln()
s
}
val sums = IntArray(n)
for(i in 0 until n) {
for(j in 0 until m) {
if(s[i][j] == 'x') {
continue
}
sums[i] += a[j]
}
sums[i] += i + 1
}
val max = sums.max()
val c = sums.count { it == max }
val flag = c == 1
val sortedA = a.mapIndexed { index, i -> index to i }.sortedByDescending { it.second }
for(i in 0 until n) {
var sum = sums[i]
var count = 0
if(sum == max && flag) {
println(0)
continue
}
var printed = false
for(j in 0 until m) {
if(max < sum) {
printed = true
println(count)
break
}
if(s[i][sortedA[j].first] == 'o') {
continue
}
sum += sortedA[j].second
count++
}
if(!printed) {
println(count)
}
}
}
flag ってなんだよ、命名センスないですねぇ…
D - Merge Slimes
解けませんでした。方針は一応立って途中まで実装したものの間に合わず。
合成を1回ずつシミュレーションすると間に合わないですが、各
ポイントは2の乗数でした。合成するたびに数が半分になっていくので、個数が2の乗数なら最終的に1匹まで減りますし、そのサイズは「元も大きさ」 × 「2の乗数」です。あぶれた分についても同じ計算を適用すれば、ある大きさのスライムは0匹か1匹まで減ります。これをMapとかで管理して全部やればいいことになります。
TreeMapを使って小さい方から処理していき、ある大きさのスライムが生まれたらそれを足し、ある大きさのスライムが1匹以下になったら消すというのをTreeMapが空になるまで繰り返します。
それだけといえばそれだけなのですが、コンテスト中はTreeMapを使えばいいということが思いつかず、普通の可変Mapを使って頑張っていて間に合いませんでした。悲しい。
コンテスト後にTLで見かけて、たしかにそれでいけるなと思ってやり直したら通りました。TreeMapが思いついていればおそらく解けたのでもったいなかったですね。
import java.util.TreeMap
import kotlin.math.pow
fun main() {
val n = readln().toInt()
val sc = Array(n) {
readln().split(" ").map { it.toLong() }.toLongArray()
}
.sortedBy { it[0] }
val treeMap = TreeMap<Long, Long>()
for((s, c) in sc) {
treeMap[s] = c
}
val ans = process(treeMap)
println(ans)
}
fun process(treeMap: TreeMap<Long, Long>): Long {
var count = 0L
while(treeMap.isNotEmpty()) {
val (s, c) = treeMap.firstEntry()
if(c < 2) {
count += c
treeMap.remove(s)
continue
}
val num = countDiv(c)
val mul = s * num
treeMap[mul] = treeMap.getOrDefault(mul, 0) + 1
treeMap[s] = c - num
}
return count
}
fun countDiv(n: Long): Long {
var num = n
var count = 0
while (true) {
num /= 2
if(num == 0L) {
break
}
count++
}
return 2.0.pow(count).toLong()
}
まあ制限時間ギリギリですが…
countDiv ってなんだよ、命名センスないですねぇ…
感想
なんというか、またしても実装力の敗北という感じです。方針は立った（合ってた）のに実装でミスって時間切れとか、非常に…残念です。
Cもしょうもないミスでペナりましたし、そもそもA～Cが通るまで40分かかっているので単純に実装が遅くてDのための時間をあまり残せなかったという感じもあります。
考察力も足りないけど、実は実装力も足りないのですね。うーん、どちらから改善していくべきなのか。ダメだった時の悲しさ度合いからすると、実装力不足のほうをなんとかするほうが重要かもしれません。仕事で役立つのもたぶんそちらだしなぁー
まあ何にせよ少しずつでも改善して、コツコツと続けたいと思います。
（執筆時間: 43分27秒）
Discussion