AtCoder Beginner Contest 271 A～Cのメモ
京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)に参加したのでメモを書いておきます。
A - 484558
Kotlinだと16進数文字列にするのどうやるっけ？と思わずググってしまいました。
Integer.toHexString()は知っていたのでそっちを使っていればもうちょっと早く解けたかも。
fun main() {
val n = readLine()!!.toInt()
println(n.toString(16).padStart(2, '0').toUpperCase())
}
B - Maintain Multiple Sequences
文字がたくさん出てきて若干混乱しましたが、結局問題文の通りに書けばOKでした。
しかし、出力が大量になるケースがあるので実行時間がちょっと怪しくてヒヤヒヤしました。
PrintWriterとか使うべきでしたね。
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val laList = List(n) {
readLine()!!.split(" ").map { it.toInt() }
}
val stList = List(q) {
readLine()!!.split(" ").map { it.toInt() }
}
for(st in stList) {
println(laList[st[0] - 1][st[1]])
}
}
PrintWriterを使った場合はこちら。
import java.io.PrintWriter
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val laList = List(n) {
readLine()!!.split(" ").map { it.toInt() }
}
val stList = List(q) {
readLine()!!.split(" ").map { it.toInt() }
}
val out = PrintWriter(System.out)
for(st in stList) {
out.println(laList[st[0] - 1][st[1]])
}
out.flush()
}
およそ半分くらいになりました。
C - Manga
全
考察
まず愚直な解法でやってみるとすると、数列をソートして前から見ていき、読みたい巻がなかったら後ろから2巻分を売る、これを行けるところまで繰り返す、という感じでできると思いました。
それで、これって計算量としてソートの分のO(N log N)でいけるのでは？と思ったのでこの愚直解を実装してみることにしました。
最初の提出
読んだ巻、または売った巻は数列から除去するという考えでArrayDequeを使ってみることにしました。今思えば実際に除去しなくても添字の操作でもよかったかもしれませんが。
またjava.util.ArrayDequeを使っていますが、kotlin.collections.ArrayDequeを使ったほうがよかったですね。
※通りません
import java.util.ArrayDeque
fun main() {
val n = readLine()!!.toInt()
val a = ArrayDeque(readLine()!!.split(" ").map { it.toInt() }.sorted())
var now = 1
while (a.isNotEmpty()) {
val first = a.first
if(first == now) {
a.pollFirst()
now++
} else {
if(a.size > 2) {
a.pollLast()
a.pollLast()
now++
} else {
break
}
}
}
println(now - 1)
}
で、これはWAとなりました。しかも多い！
ただ、実行時間は十分速いのでやはり愚直解でもいけるという感触を得ました。
考察と再提出（１）
色々なケースを試してみて、このコードだとdequeに残った数が2つの場合、それらを売ればもう1巻読めるのにbreakしてしまうのがおかしいと気づきました。
たとえば以下のようなケースです。
4
1 2 4 5
4, 5を売れば3巻まで読めるのに出力が2になってしまいます。
なのでそれに対処したコードを提出します。（ツギハギ…）
※通りません
import java.util.ArrayDeque
fun main() {
val n = readLine()!!.toInt()
val a = ArrayDeque(readLine()!!.split(" ").map { it.toInt() }.sorted())
var now = 1
while (a.isNotEmpty()) {
val first = a.first
if(first == now) {
a.pollFirst()
now++
} else {
if(a.size > 2) {
a.pollLast()
a.pollLast()
now++
} else if(a.size == 2) {
now++
break
} else {
break
}
}
}
println(now - 1)
}
WAは減ったけどまだあります。まあ13個もあったのだから他にも問題があるだろうと考えるべきでしたね…
考察と再提出（２）
また色々なケースを試してみて、同じ巻を複数持っている場合におかしくなることがわかりました。
たとえば以下のようなケースです。
5
1 2 2 3 4
一見して4巻まで読めるとわかりますが、出力は3になってしまいます。3巻目を期待しているときに2冊目の2巻が来ることで、後ろの3巻と4巻を売るという暴挙に出てしまいます。
要するに期待している巻数より小さい巻が来たら、それは売っていいので末尾に移動させれば帳尻が合います。その方針で実装してみます。
※通りません
import java.util.ArrayDeque
fun main() {
readLine()!!.toInt()
val a = ArrayDeque(readLine()!!.split(" ").map { it.toInt() }.sorted())
var now = 1
var count = 0
while (a.isNotEmpty()) {
val first = a.first
if(first < now) {
a.pollFirst()
a.addLast(first)
continue
}
if(first == now) {
a.pollFirst()
now++
count++
} else {
if(a.size >= 2) {
a.pollLast()
a.pollLast()
now++
count++
} else {
break
}
}
}
println(count)
}
色々いじったので細部が変わっていますが、以下が追加されたのが特徴です。
if(first < now) {
a.pollFirst()
a.addLast(first)
continue
}
今度はTLEになりました…
考察と再提出（３）
計算量の問題はないと思っていましたが、上記の実装だと要素を位置だけ変えてやり直しなのでループ回数が増えてしまうんですね…
考察が甘かったことに気づいて心が折れそうになりましたが、書き直す時間もないのでこのまま突っ切ってみようと思いました。
とにかく問題なのは重複です。重複さえなけば問題ないはず。なので重複を除去してみることを考えました。単純に除去しただけだと売るための巻が減るのでダメなのですが、売るための巻という意味だと数字は別に何でもいいので、除去した件数分だけダミーデータを末尾に追加すればいけるのでは、と思いました。
除去した件数は、除去前と後で件数の差分を見ればわかります。
ダミーデータとして0を入れていますが、aの入力としてあり得ない値なら何でもいいはずです。
import java.util.ArrayDeque
fun main() {
readLine()!!.toInt()
val ta = readLine()!!.split(" ").map { it.toInt() }.sorted()
val b = ta.distinct()
val diff = ta.size - b.size
val a = ArrayDeque(b)
repeat(diff) {
a.addLast(0)
}
var now = 1
var count = 0
while (a.isNotEmpty()) {
val first = a.first
if(first == now) {
a.pollFirst()
now++
count++
} else {
if(a.size >= 2) {
a.pollLast()
a.pollLast()
now++
count++
} else {
break
}
}
}
println(count)
}
やったぜ！！！
kotlin.collections.ArrayDequeを使ってみる
コンテスト後、kotlin.collections.ArrayDequeを使って書き直してみました。（ついでに気になっていた部分も修正）
java.util.ArrayDequeとはメソッド名が異なるのと、少なくともAtCoderで対応している1.3.71時点では@ExperimentalStdlibApiを付けないと使えないということがわかりました。
だったらjava.util.ArrayDequeでいいかな…
import kotlin.collections.ArrayDeque
@ExperimentalStdlibApi
fun main() {
readLine()!!.toInt()
val ta = readLine()!!.split(" ").map { it.toInt() }.sorted()
val b = ta.distinct()
val diff = ta.size - b.size
val a = ArrayDeque(b)
repeat(diff) {
a.addLast(0)
}
var now = 1
var count = 0
while (a.isNotEmpty()) {
val first = a.first()
if(first == now) {
a.removeFirst()
now++
count++
} else if(a.size >= 2) {
a.removeLast()
a.removeLast()
now++
count++
} else {
break
}
}
println(count)
}
感想
AやBで特に詰まらず、Cも最終的には解けたのでけっこう満足できた回でした。
ただBで少しヒヤッとしたのと、Cで3ペナも食らったのは反省点ですね。
出力がどれくらいになりうるのかは今後は気をつけて見るようにしたいです。
あとはCの3ペナですが、少なくともWAに関してはちゃんとテストしていれば防げたのですが、現状はCは解けないことが多いので、WAで心が折れずに最後まで取り組めたのはむしろ良かったと考えたいと思います。
Cがあまり解けない → CをWA出てもいいから通す → Cをノーペナで通す
という感じで段階的に行きたいと思います。まずはWA出てもいいので通すという段階を目指し、C問題の過去問に取り組んでいきたいです。
Discussion