AtCoder Beginner Contest 301参加記（A～D）
パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）に参加したので記録を残します。
久しぶりの参加になりましたが、ノーペナ3完で無難な感じの結果になりました。
A - Overall Winner
それぞれの勝利数を数えて比較しました。同じである場合は最後の文字を見ることで、勝利数がその数に到達するのが遅かったほうがわかります。遅くなかったほうが総合勝者です。
fun main() {
val n = readLine()!!.toInt()
val s = readLine()!!
val t = s.count { it == 'T' }
val a = s.count { it == 'A' }
if(t > a) {
println("T")
} else if(a > t){
println("A")
} else {
if(s.last() == 'A') {
println("T")
} else {
println("A")
}
}
}
B - Fill the Gaps
力技で実装しました。計算量も全く考えていません。
解説にも書かれていましたが、可変リストの末尾以外への追加は、追加する箇所以降の値をずらす処理が発生するので線形時間かかります。しかし、この問題だと制約が小さいので特に気にせずそういう操作も行いました。
明示はされていませんが、操作が終了しないことはないという想定で、操作終了条件を満たすまでずっとループして操作します。
走査中のリストの大きさが変わるような実装は経験上とてもバグらせやすいので本当はやりたくなかったのですが、他に方法も思いつかず。添え字操作が怖かったです…
import kotlin.math.abs
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
loop@while (!check(a)) {
var i = 0
while (i < a.size) {
if(i != 0) {
if(abs(a[i-1] - a[i]) != 1) {
if (a[i-1] > a[i]) {
var diff = 1
for(j in a[i-1] + 1 until a[i]) {
a.add(i + diff, j)
diff++
}
} else {
var diff = 1
for(j in a[i-1] - 1 downTo a[i] + 1) {
a.add(i + diff, j)
diff++
}
}
continue@loop
}
}
if(i != a.size - 1) {
if(abs(a[i] - a[i + 1]) != 1) {
if (a[i] > a[i+1]) {
var diff = 1
for(j in a[i] - 1 downTo a[i+1] + 1) {
a.add(i + diff, j)
diff++
}
} else {
var diff = 1
for(j in a[i] + 1 until a[i+1]) {
a.add(i + diff, j)
diff++
}
}
continue@loop
}
}
i++
}
}
println(a.joinToString(" "))
}
fun check(a: List<Int>): Boolean {
for(i in a.indices) {
if(i != 0) {
if(abs(a[i-1] - a[i]) != 1) {
return false
}
}
if(i != a.size - 1) {
if(abs(a[i] - a[i + 1]) != 1) {
return false
}
}
}
return true
}
C - AtCoder Cards
ソートする…？と最初に思ったのですが、@を考慮したうえでいい感じにソートなんてことはできなさそうなので諦めました。
自由に並べ替えが可能なので何がどの位置にあるかは関係なく、各文字の個数さえ合っていればいいと気づきました。
@から置き換えが可能なのは「a, t, c, o, d, e, r」だけで、それらと@以外の文字について個数が一致しないものが一つでもあれば結果はNoです。
置き換え可能な文字については、個数が一致しなくて、もう一方の文字列に含まれる@の個数を消費することで個数を一致させることができるなら、その時点ではNoとせずチェックを続行します。（逆に個数が一致すれば、@について考慮せずチェック続行です）
@の消費については、最初に個数を数えておいて、消費する分だけ減らすことで表現できます。@の個数が足りない場合は答えはNoです。
@が最初からない場合もありますが、それは単純に@の個数が0として表現します。
最後に、@の残り個数が一致していたらYesとしています。しかし、今思えばこれはいらなかったかも…？
fun main() {
val s = readLine()!!
val t = readLine()!!
val sMap = mutableMapOf<Char, Int>()
val tMap = mutableMapOf<Char, Int>()
for(i in s.indices) {
sMap[s[i]] = sMap.getOrDefault(s[i], 0) + 1
}
for (i in s.indices) {
tMap[t[i]] = tMap.getOrDefault(t[i], 0) + 1
}
var sAtCount = sMap.getOrDefault('@', 0)
var tAtCount = tMap.getOrDefault('@', 0)
val set = "atcoder".toSet()
for(c in "abcdefghijklmnopqrstuvwxyz") {
if(c !in set) {
if(!sMap.containsKey(c) && !tMap.containsKey(c)) {
continue
}
if(sMap.containsKey(c) != tMap.containsKey(c)) {
println("No")
return
}
if(sMap[c]!! != tMap[c]) {
println("No")
return
}
} else {
val sCount = sMap.getOrDefault(c, 0)
val tCount = tMap.getOrDefault(c, 0)
if(sCount == tCount) {
continue
}
if(sCount > tCount) {
val diff = sCount - tCount
if(diff <= tAtCount) {
tAtCount -= diff
} else {
println("No")
return
}
} else {
val diff = tCount - sCount
if (diff <= sAtCount) {
sAtCount -= diff
} else {
println("No")
return
}
}
}
}
if(sAtCount == tAtCount) {
println("Yes")
} else {
println("No")
}
}
D - Bitmask
解けなかった問題です。最初は制約についてちゃんと理解しておらず、再帰を使って愚直に全パターンを洗い出しました。
しかしTLE。最大で60桁なので最大で
fun main() {
val s = readLine()!!
val n = readLine()!!.toLong()
val nums = s.toMutableList()
rec(nums)
println(list.filter { it <= n }.max() ?: -1)
}
val list = mutableListOf<Long>()
fun rec(nums: MutableList<Char>) {
if(!nums.contains('?')) {
list.add(nums.joinToString("").toLong(2))
return
}
val i = nums.indexOf('?')
nums[i] = '0'
rec(nums)
nums[i] = '1'
rec(nums)
nums[i] = '?'
}
この再帰解法から一歩進めて、メモ化再帰みたいな感じでできないかなーと考えていたのですが時間切れ。
解説を読むと、もっと簡単な方法があるようでした。
?を全部0で置き換えてもNより大きいのであれば答えは-1、そうでない場合は一つ一つ1に置き換えて、置き換えた桁より後の?は全部0として、それでN以下の値の最大値が答えと。
1に置き換えてもN以下なのであれば、0に置き換えた場合の値は絶対に答えではないので無視していいです。
1に置き換えたときにNより大きくなるのであればそれは答えではないですが、0に置き換えた場合の値は答えとしてあり得るかもしれないので0にして次の桁に進みます。
この考え方だと、1に置き換えたとしても0に置き換えたとしてもその時点でもうその桁は確定するってことですね。もう片方に置き換えた場合について考えなくていいので、結果としてSの全桁を1回走査すればいいので速いと。天才ですね…
まあ、置き換えた文字を文字列として結合するのは線形時間かかりそうですが、最大でも60桁しかないので問題なし。
import kotlin.math.max
fun main() {
val s = readLine()!!
val n = readLine()!!.toLong()
val digits = s.replace('?', '0').toMutableList()
if(digits.joinToString("").toLong(2) > n) {
println(-1)
return
}
var ans = -1L
for(i in s.indices) {
if(s[i] == '?') {
digits[i] = '1'
}
val num = digits.joinToString("").toLong(2)
if(num <= n) {
ans = max(ans, num)
} else {
digits[i] = '0'
}
}
println(ans)
}
感想
コンテスト参加は1ヶ月ぶりくらいになってしまったので冷え覚悟と思っていましたが、意外となんとかなりました。
今回はわりと実装ゲーという感じでしたが、細かい部分で意外とバグらせずに実装できてよかったです。競プロをしばらくやってみて、実装の凡ミスが減ったような気がしています。コンテストのプレッシャーの中で速く正確に実装するというのはなかなか良い訓練になりますね。
競プロは役に立つ。
（執筆時間: 50分3秒）
Discussion