AtCoder Beginner Contest 291 A～Cのメモ
AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）に参加したので記録を残します。
今回は3完です。
A - camel Case
大文字を抽出して、それの位置を再度探索するという二度手間な実装になりました。
コンテスト中はなぜかfor文を使うという発想が出てきませんでした。手続き脳なんだか関数型脳なんだかよくわかりません。グダグダ。
fun main() {
val s = readLine()!!
println(s.indexOf(s.filter { it.isUpperCase() }.first())+ 1)
}
あと今確認したらindexOfFirst()というメソッドもあり、これを使ってもよかったですね。
B - Trimmed Mean
最初はsubList（Pythonとかでいうとスライスのようなもの）を使おうとしたのですが、必要な部分だけ取り出せばいいのになんか不要な部分を除去するという発想になっていて混乱しました。
結局その不要な部分を除去するというのをそのまま実装してました。
@OptIn(kotlin.ExperimentalStdlibApi::class)
fun main() {
val n = readLine()!!.toInt()
val x = readLine()!!.split(" ").map { it.toInt() }
.sorted()
.toMutableList()
repeat(n) {
x.removeLast()
}
repeat(n) {
x.removeFirst()
}
println(x.sum().toDouble() / (n*3))
}
そもそもMutableListにこんなメソッドがあるとは知りませんでしたが…
今のバージョンだと @OptIn(kotlin.ExperimentalStdlibApi::class) を付けないと使えませんでした。
removeLast() はともかく removeFirst() は計算量としてはダメそうですが、まあ制約が小さいのでいいでしょうという感じです。
C - LRUD Instructions 2
C問題としては簡単めで、やるだけですね。同じ場所にいたことがあるかどうかの判定は高速に実行する必要がありますが、MapなりSetなりを使えばいいです。Setのほうが簡単だけどなぜかMapを使ってました。
初期位置は原点なので、そこにいたことがあるという初期化を忘れないようにします。忘れてましたが。サンプルが親切でなければペナってたかも……
2点の組み合わせで保持する必要があるのでPairを使っています。KotlinのPairはハッシュテーブルで使用できます。遅い気がしますが。
fun main() {
val n = readLine()!!.toInt()
val s = readLine()!!
val seen = mutableMapOf<Pair<Int, Int>, Boolean>()
seen[0 to 0] = true
var x = 0
var y = 0
for(c in s) {
when (c) {
'R' -> {
x++
}
'L' -> {
x--
}
'U' -> {
y++
}
'D' -> {
y--
}
}
if(seen.getOrDefault(y to x, false)) {
println("Yes")
return
}
seen[y to x] = true
}
println("No")
}
x to yでなく逆にしているのはなんとなくです。読み書き時で一致していればどっちでもよさそうです。
実は最初二次元配列で管理しようとして、そもそも要素を何個確保すればいいかわからんってなってました。今回グダグダすぎて笑います。
D - Flip Cards
DPだとしたら起点となる値が必要で、1とかで初期化するのがよくあるパターンですが、この問題の場合は初期状態が条件を満たすとは限らないので固定で1で初期化できなくない？と思いました。
しかし、解説を見ると普通にそうしてますね…
正直解説を見ても全然わからないので明日以降頑張ります…
感想
A～Cまではなんかグダグダで数分くらいはロスしてたので残念でした。まあ長時間詰まったりペナったりしなかったのでいいか。
DはDPとしては典型らしいのですが全然わからないので、まだまだですね。DP多少はわかったつもりだったけど、初歩の初歩くらいのパターンを記憶したというだけで全然理解はしてなかったのかも。
（執筆時間: 27分29秒）
Discussion