📘

ABC 048 C - Boxes and Candiesのメモ

2023/05/19に公開

AtCoder

競プロ

tech

解いてみました。

考察

先頭から見ていって、その場その場で条件を満たすようにして、それを末尾まで繰り返したら解けないかなあと思ったのですが、それで良さそうだったのでそれで実装しました。

まず先頭とその次を見て、それらの合計が $x$ よりも大きければ、その「次」のほうを減らします。最小手数なので、合計が $x$ になる分だけ減らします。具体的には、2つの合計から $x$ を引いた数です。いくつ減らしたのかは記録します。その操作を末尾まで繰り返して、「いくつ減らしたのか」の総和が答えです。

ポイントは、ある箇所で一度条件を満たしたら、他の箇所で何をしようとも条件が崩れることはないということです。条件は総和が $x$ 以下であることですが、操作は減らすことしかできませんし、一旦 $x$ 以下になったらそれからいくら減らしても条件を満たさなくなることはありません。
そのため、ある箇所とその次の2か所についてだけの問題として分解できて、それを全部に対して行えばいいということになります。

実装

fun main() {
    val (n, x) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    var ans = 0L
    for(i in 0 until n - 1) {
        if(a[i] < 0) {
            a[i] = 0
        }

        val sum = a[i] + a[i+1]

        if(sum > x) {
            val diff = sum - x
            a[i+1] -= diff
            ans += diff
        }
    }

    println(ans)
}

本来であればa[i+1]を0まで減らしてもまだ条件を満たさない場合はa[i]からも引かないと条件を満たす数列にならないのですが、答えとして出力するのは操作回数だけなので、数列が条件を満たさないものになっても問題ありません。
なので実装としてはa[i]とa[i+1]の大小関係は気にせず固定でa[i+1]から引いています。これによってa[i+1]が負の値になることもありますが、問題ありません。本来はa[i]から引くはずだった分なのですが、a[i]を再度参照することはないので。
ただ、a[i+1]の位置が次回のa[i]になったときの計算が狂わないように補正する必要はあります。

（執筆時間: 29分29秒）
↑偶然だよ

考察

実装

Discussion