AtCoder Beginner Contest 322参加記（A～C）
AtCoder Beginner Contest 322に参加したので記録を残します。
今回も3完です。
A - First ABC 2
indexOfを使うだけなんですが…
s.indexOf("ABC") >= 0 の部分が s.indexOf("ABC") > 0 になっていてペナりました。やばい。
indexOfを2回呼ぶ必要はもちろんないのですが、テンパっていてこうなりました。
fun main() {
val n = readln().toInt()
val s = readln()
if(s.indexOf("ABC") >= 0) {
println(s.indexOf("ABC") + 1)
} else {
println(-1)
}
}
B - Prefix and Suffix
startsWith と endsWithで調べます。ssというのは、suffixの略でsにしようと思ったけど、sは既に使っていたのでssになりました。
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val s = readln()
val t = readln()
val p = t.startsWith(s)
val ss = t.endsWith(s)
if(p && ss) {
println(0)
} else if(p) {
println(1)
} else if(ss) {
println(2)
} else {
println(3)
}
}
C - Festival
存在しない場合は、KotlinのbinarySearch()では戻り値に1を足して符号を反転させると、その要素があったとしたらその位置のはずという値がわかります。これは先週学んだことだったのですが、早速役に立ちました。嬉しい。
import java.io.PrintWriter
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val out = PrintWriter(System.out)
for(i in 1 .. n) {
val tmp = a.binarySearch(i)
val index = if(tmp < 0) {
-(tmp + 1)
} else {
tmp
}
println(a[index] - i)
}
out.flush()
}
1から- iで補正して出力です。
D - Polyomino
なんかやばそうなので飛ばしました。解ける気がしないのと、順位表を見ると解けている人が明らかに少なかったので…
E - Product Development
制約が小さければbit全探索で解けるけど実際には制約が大きくて無理、なのでDPっぽいとは思いましたが、管理したい値（パラメーター）が最大5つなので、まさか5次元DP？もしくは6次元DP？？
一応やってみようと思いましたが、5次元だとか6次元だとかだとデータの状態をイメージできなくて全然無理でした。
5次元とかにしないで2次元配列を5つ用意するのではダメなのかなと思ったりもしましたが、個別にDPで求めても得られるのはコストの値だけで、どの開発案を採用したのかはもはやわからなくなっているのでまとめて扱わないとダメでしたね。
解説をチラ見した感じだと2次元DPで解けるようでした。5次元DPとかをイメージできるようになるよりは2次元DPで解けるようになるための考え方を学んだ方がよさそうです。シンプルに興味があるので、そのうち解説ACしようと思います。
感想
Aでペナった時点でもうダメかと思いましたが、Cは比較的（あくまでも比較的）早く解けたので事なきを得ました。（+3）
不甲斐ないですが、まあいつものこととも言えます…
体調が悪いときはABCに出るのが怖いと感じてしまっていましたが、体調が良くなるにつれて、普通にABCに出たいと思えるようになったので良かったです。
あまり精進できてない以上はレートの上昇はあまり期待できないので、とりあえずRated参加できているだけで良いほうかなと思います。
（執筆時間: 31分53秒）
Discussion