AtCoder Beginner Contest 306参加記（A～D）
トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)に参加したので記録を残します。
今回はなんとか4完で、一応連敗は阻止したという感じです。残念ながらUnratedとなったのでレート変動はありませんが。
（今回の内容と関係ないけど、ここまでUnratedが続くとAtCoderの死活問題ですよね…負けるなAtCoder）
A - Echo
文字を一通り見て、それぞれ2回ずつ出力すればいいです。全部結合してから最後に一回出力のほうが楽だったかもしれません。
fun main() {
val n = readLine()!!.toInt()
val s = readLine()!!
for(i in 0 until n) {
print(s[i])
print(s[i])
}
println()
}
B - Base 2
計算するだけなのですが、Longだとオーバーフローするので注意が必要です。（ここで2敗）
Longでもオーバーフローするような計算問題は初めて見ました。そのような問題は出さないような暗黙の了解があると思いこんでいたのでびっくりしました。
（文字列として扱い、計算しないことで回避できるという問題はけっこうありましたが、計算する、つまり数値として扱わないといけない問題は初めて見ました）
問題文を読んでオーバーフローすることに気づけなかったのは私のミスでしかないので、文句があるわけではないです。Longで扱えないこともあり得ると認識を改めます。
Longで扱えないとなると、多倍長整数型か符号なし64bit整数型で扱うことになります。
今回は多倍長整数型であるBigIntegerを使いました。
（符号なし整数はKotlinにはないと思い込んでたけど、実はあることにコンテスト後に気づきました）
import java.math.BigInteger
fun main() {
val a = readLine()!!.split(" ").map { it.toInt() }
var ans = BigInteger.ZERO
for(i in 0 until 64) {
if(a[i] == 1) {
ans += pow(i)
}
}
println(ans)
}
private fun pow(i: Int): BigInteger {
if(i == 0) {
return BigInteger.ONE
}
var ans = BigInteger.ONE
for(j in 0 until i) {
ans *= BigInteger("2")
}
return ans
}
Doubleのpow()を使ったら微妙に誤差があって2度目のWAが出てしまいました… なのでpow()は自作しました。
ただ、考えてみたらこれって反転させるとただの2進数ですね。なので、これだけで良かったようです。
fun main() {
val a = readLine()!!.split(" ").map { it.toInt() }
val n = a.reversed().joinToString("").toULong(2)
println(n)
}
C - Centers
よくある
KotlinだとsortedByを使うと楽ですね。
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val map = mutableMapOf<Int, Int>()
val bucket = IntArray(n * 3 + 10)
for(i in 0 until n * 3) {
val num = a[i]
bucket[num]++
if(bucket[num] == 2) {
map[num] = i + 1
}
}
val list = map.map { it.key to it.value }.sortedBy { it.second }.map { it.first }
println(list.joinToString(" "))
}
D - Poisonous Full-Course
美味しさのためなら毒を食うことも厭わない高橋くん、ヤベェな
これはすごく典型的なDPの問題と感じました。これは解けなきゃいけない問題と思いましたが、最近DPを書いていないので自分の過去記事を見たりして思い出していきました。
まずDPとか以前に、そもそも食べるかどうかをどのようなルールで行えばいいのかを考えます。
解毒剤入りについては、美味しさが正の数であれば食べるデメリットがないので食べます。
解毒剤入りで美味しさが負の数の場合ですが、これは食べたほうがいい場合もあります。その時点では美味しさの総和が減りますが、代わりにお腹壊し状態から抜けられるメリットがあります。次の料理は非常に美味しい毒入りかもしれず、それを食べることで結果的に美味しさの総和を増やせる可能性があります。
逆に、お腹を壊していないのであれば美味しさが負の数の料理を食べるメリットはありません。
毒入りを続けて2回食べたら死んでしまいますが、逆に1回であればセーフです。なので毒入りであっても美味しさが正の数であれば食べた方がいい場合があります。かといって、ここで食べてお腹を壊し、その次出たさらに美味しい料理を逃したら美味しさの総和が減ることもあり得ます。
毒入りかつ美味しさが負の数であれば食べるメリットが全く無いので必ずスルーします。
上記をもとにDP表を作り、その料理を食べた時点であり得る美味しさの総和の最大値を求めていきます。どんどん埋めていって、最後の料理を食べた時点であり得る美味しさの最大値が答えです。
お腹を壊しているかいないかの状態があり得るので、二次元配列にすることで「お腹を壊していない場合の最大値」と「お腹を壊している場合の最大値」を両方保持します。
この場合、行がお腹を壊しているかいないかの状態、列が料理の種類、値がそのi個の料理を食べた時点で到達可能な最大値、です。
2次元といってもお腹を壊しているかいないかの2つの状態だけ管理するので、計算量としては1次元配列と同じで定数倍が少し重いだけ（無視できる程度）と考えられます。
各料理を食べるか食べないかは、その時点で注目している料理の美味しさを前回の最大値に足すか足さないかで表現されます。
前回までの蓄積を信じて今回の料理を食べるか食べないかだけを考える、それを最後まで繰り返すことで最終的に欲しい値が結果的に求められるというのがDPですね。
コードはこんな感じです。（コメントは後から追加しました）
import kotlin.math.max
fun main() {
val n = readLine()!!.toInt()
val xy = List(n) {
val (x, y) = readLine()!!.split(" ").map { it.toLong() }
x to y
}
// 腹を壊しているかどうかで分けて考えるため二次元配列（0: お腹を壊していない, 1: お腹を壊している）
val dp = Array(2) { LongArray(n + 10) }
// i個目の料理を処理（食べる or 下げてもらう）を実行した時点であり得る最大値がdp[0][i]、dp[1][i]に入るように埋める
for(i in 1 .. n) {
val (x, y) = xy[i - 1]
// 解毒剤入り
if(x == 0L) {
// お腹を壊している場合、壊していない場合の両方から遷移可能なのでそのうち大きい方を採用
// ただし、美味しさがマイナスの場合は食べないように注意
// 食べない場合は増減はなく単純に引き継ぐ（それ以降の計算のために必要）
dp[0][i] += listOf(dp[0][i-1] + y, dp[1][i-1] + y, dp[0][i-1]).max()!!
// この料理を食べた時点でお腹を壊している状態はあり得ないが、後続の計算のために前の値は引き継いでおく
dp[1][i] = dp[1][i-1]
} else {
// 毒入り
// この料理を食べた時点でお腹を壊してない状態はあり得ないが、後続の計算のために前の値は引き継いでおく
dp[0][i] = dp[0][i-1]
if(y < 0) {
// 美味しさが負の数の場合は食べるメリットがないので食べず、単純に引き継ぐ
dp[1][i] = dp[1][i-1]
} else {
// お腹を壊していない状態からの遷移はあり得る
// お腹を壊している状態からの遷移はあり得ない（死んじゃうので）
// お腹を壊していない状態の最大値 + yよりも、お腹を壊している場合の最大値のほうが大きい場合は食べない
dp[1][i] += max(dp[1][i-1], dp[0][i-1] + y)
}
}
}
val ans = max(dp[0].max()!!, dp[1].max()!!)
println(max(0, ans))
}
食べない場合は引き継ぐ、というのを忘れたりしてWAが出たりもしまいしたが、ギリギリACが間に合ってよかったです。
感想
前回は目を覆いたくなるような結果だったので今回も怖かったのですが、意外となんとかなってよかったです。
まあグリッド系の問題が出なかったからというのもありますが…
これからもコツコツとやっていきます。
（執筆時間: 53分11秒）
Discussion