👋
ABC 368 C - Triple Attackのメモ
解いてみました。
考察
3回の攻撃につき5のダメージを与えると考えると、HPを5で割った商で「3回の塊」の個数がわかります。少なくとも、その個数 × 3の回数は攻撃します。余りがある場合、余りが1か2の場合は単純にその回数追加で攻撃、3か4であれば3回追加攻撃です。4の時も3回でいいのは、その時与えるダメージは3だからです。この計算で、1体当たりの攻撃回数を定数時間で求められます。
基本的にはこれを全ての敵に対して計算すればいいのですが、少し考慮が必要な点があります。前の敵を倒した時点での攻撃回数が3の倍数なら気にしなくていいのですが、そうではない場合はダメージ3を与える回数の周期がずれます。攻撃回数を3で割った余りが1なら2回、2なら1回攻撃させることで周期を補正できます。ただし、その補正のための攻撃でHPが0以下になるケースも考慮が必要です。
ついでに、補正のための攻撃で3ダメージ与えるケースがあることにも考慮が必要ですね。（これの見落とし+αで1ペナもらいました）
実装
import kotlin.math.min
fun main() {
val n = readln().toInt()
val hList = readln().split(" ").map { it.toInt() }
val map = mapOf(
0 to 0,
1 to 2,
2 to 1,
)
var t = 0L
for(h in hList) {
var hi = h
val tMod = t % 3
var continueFlag = false
for(i in 0 until map[tMod.toInt()]!!) {
t++
if(t % 3 == 0L) {
hi -= 3
} else {
hi--
}
if(hi <= 0) {
continueFlag = true
break
}
}
if(continueFlag) {
continue
}
val hDiv = hi / 5
t += hDiv * 3
val hMod = hi % 5
t += min(3, hMod)
}
println(t)
}
Discussion