AtCoder Beginner Contest 294 A～Eのメモ
AtCoder Beginner Contest 294に参加したので記録を残します。
今回は1ペナ4完で、Eはコンテスト後に解説のコードをほぼ丸写ししただけのものとなります。
A - Filter
偶数を取り出すだけです。こういうのはループよりリスト操作の高階関数が効果的です。
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
println(a.filter { it % 2 == 0 }.joinToString(" "))
}
39秒で提出できたのでこの瞬間だけは良い順位だったはず…ｗ
B - ASCII Art
数値を文字に置き換えるだけですね。ASCIIコードは覚えてないので慌てて調べましたが、慌ててたので間違えて小文字に変換しちゃいました。なので慌てて toUpperCase() を付け足しました。ひどい。
慌ててたので余分な空行ができました。慌てすぎ。
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val a = List(h) {
readLine()!!.split(" ").map { it.toInt() }
}
for(i in a.indices) {
println(a[i].map { if(it == 0) "." else (it+96).toChar().toUpperCase() }.joinToString(""))
}
}
コンテスト中はねこかわいいとか思う余裕はありませんでした。
なお、このコードはIDE上では警告が出ていました。（黄色くなっている部分）
コンテスト中は急いでいたので無視してそのまま提出しましたが、何だったのか気になってコンテスト後に見てみました。
Kotlinにはいわゆる「三項演算子」は存在しないためif式を使っていますが、このコードだと条件にマッチした場合はString、しなかった場合はCharが返るので型が一致せず、このif式の評価値の型はAny型になってしまうよという警告でした。Any型は全ての型の共通の親クラスで、JavaでいうならObject型のようなものです。StringとCharでは他の共通の親クラスはなく、Anyと評価するしかなかったということみたいです。
それで、たぶん joinToString() の中で toString() を呼ぶとかしているので結果的には問題なかったようですね。
C - Merge Sequences
実際に
線形探索だと間に合わないですが、ソート済みの数列に対する探索なので二分探索が使えます。重複要素もないので単純に組み込みの binarySearch() を使うだけです。
（まあ今思えば、本当に重複要素がないと言えるのかについてコンテスト中はちゃんと理解してませんでしたが…狭義単調増加なので結果的には合ってそう）
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }
val b = readLine()!!.split(" ").map { it.toInt() }
val c = (a + b).sorted()
println(a.map { c.binarySearch(it) + 1 }.joinToString(" "))
println(b.map { c.binarySearch(it) + 1 }.joinToString(" "))
}
ここまでで9分ちょい。自分史上最速かもしれません。ここまでは良かったんですがね。
D - Bank
なんか問題文の読解に時間がかかってしまいました。なぜか、「すでに受付に呼ばれているが受付に行っていない人」の意味がよくわかりませんでした。今思えばそのまんまの意味なのですが…
直感的に、賢いデータ構造を使えば解ける系統の問題だと思いました。
ポイントは「すでに受付に呼ばれているが受付に行っていない人」をどう管理するかなんですが、最初はPriorityQueueでやろうとしていて悩みました。1の時に追加、3の時に最小値を取り出す、は高速にできますが、2の時に削除、は O(N) かかるからです。
ただ、結果的には必要な操作が全部高速に実行できる赤黒木があるじゃないかと思い至りました。そこまでに時間がかかった…
（最小値の取得は O(1)、追加と削除は O(log N)かな？）
赤黒木の実装としてKotlin（というかJava）はTreeSetがあるのでこれを使います。
あとは出力が大量になるのでPrintWriterでバッファリングします。
import java.io.PrintWriter
import java.util.PriorityQueue
import java.util.TreeSet
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val list = (1..n).toList()
val calledSet = mutableSetOf<Int>()
val noCallQueue = java.util.ArrayDeque(list)
val notGoSet = list.toMutableSet()
val calledAndNotGoSet = TreeSet<Int>()
val out = PrintWriter(System.out)
repeat(q) {
val event = readLine()!!.split(" ").map { it.toInt() }
if(event.first() == 1) {
val h = noCallQueue.removeFirst()
calledSet.add(h)
calledAndNotGoSet.add(h)
} else if(event.first() == 2) {
val (_, x) = event
notGoSet.remove(x)
calledAndNotGoSet.remove(x)
} else if(event.first() == 3) {
out.println(calledAndNotGoSet.first())
}
}
out.flush()
}
試行段階で追加したいらないやつもたくさんあるけどまあ通るでしょと提出しましたがまさかのTLE。うーん、計算量的には問題ないはずなのですが。
あれこれ見直しましたがやはり計算量的には問題なさそうで、定数倍の問題っぽかったです。
とりあえずいらないのを消して、「受付に呼ばれていない人」をキューで管理してたけど別に配列でいいじゃんと思って変更して、ついでに入力はBufferedReaderを使ったほうが微妙に速いという（ほんとかどうかわからない）経験則があるのでそちらに変えて、お祈り提出。
import java.io.PrintWriter
import java.util.*
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val list = (1..n).toList()
var i = 0
val calledAndNotGoSet = TreeSet<Int>()
val br = System.`in`.bufferedReader()
val out = PrintWriter(System.out)
repeat(q) {
val event = br.readLine()!!.split(" ").map { it.toInt() }
if(event.first() == 1) {
calledAndNotGoSet.add(list[i])
i++
} else if(event.first() == 2) {
calledAndNotGoSet.remove(event[1])
} else {
out.println(calledAndNotGoSet.first())
}
}
out.flush()
}
通りました。あれこれ同時にやったのでどれが功を奏したのかわからないですが、現時点ではまだ調べられてないです。
まさか定数倍に殺されるとは…（もしくは自分の勘違いか？）
ここまでで44分ちょい + 1ペナ。なかなか痛い。
E - 2xN Grid
これは解けませんでした。とりあえず連長圧縮（ランレングス圧縮）がどのようなものかは知っていて、展開してからチェックだと制約的に間に合わない（そもそもメモリが足りない？）が、圧縮された状態のままチェックするなら間に合う、というところまでは理解しました。しかし実装できず。
解説を見ると発想までは合っていましたが、まあ実装できなければ0点です。それはそう。
コンテスト後に通したコードですが、正直解説のコードをほぼ書き写しただけです。細部を理解できませんでした。共通区間を扱う系は本当にダメです。共通区間を調べるA問題（ABCのA問題）で爆死したことがあるのを思い出してしまいました。
import kotlin.math.max
import kotlin.math.min
fun main() {
val (l, n1, n2) = readLine()!!.split(" ").map { it.toLong() }
val vl1 = List(n1.toInt()) {
readLine()!!.split(" ").map { it.toLong() }
}
val vl2 = List(n2.toInt()) {
readLine()!!.split(" ").map { it.toLong() }
}
var p = 0L
var q = 0L
var i = 0
var j = 0
var ans = 0L
while (i < n1 && j < n2) {
if(vl1[i][0] == vl2[j][0]) {
ans += min(p + vl1[i][1], q + vl2[j][1]) - max(p, q)
}
if (p + vl1[i][1] < q + vl2[j][1]) {
p += vl1[i][1]
i += 1
} else {
q += vl2[j][1]
j += 1
}
}
println(ans)
}
考え方自体はわかるのと、右端の位置が一致している場合も
感想
うーん、まあ…冷えなかっただけヨシ！
お疲れモードなのでゆっくりやります。
（執筆時間: 58分8秒）
Discussion