🍣

ABC167 C - Skill Upのメモ

2022/11/22に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

ABC167はリアルタイムで参加してたっぽいのでこの問題も初見ではないはずですが、提出履歴がなかったので当時は理解できなかったようです。

考察と解答

最近の癖でDPを最初に思いつきましたが、できるとしても3次元になりそうだったので、さすがに別の解法があるかなと思いました。
それで、制約を見ると非常に緩いことがわかったのでbit全探索で解けそうと考えました。

import kotlin.math.min

fun main() {
    val (n, m, x) = readLine()!!.split(" ").map { it.toInt() }
    val ca = List(n) {
        readLine()!!.split(" ").map { it.toInt() }
    }
    var ans = Int.MAX_VALUE

    for(bit in 0 until (1 shl n)) {
        var sum = 0
        val aSum = IntArray(m)
        for(i in 0 until n) {
            if(bit and (1 shl i) != 0) {
                sum += ca[i][0]
                val a = ca[i].subList(1, ca[i].size)

                for(j in 0 until m) {
                    aSum[j] += a[j]
                }
            }
        }
        if(aSum.all { it >= x }) {
            ans = min(ans, sum)
        }
    }
    if(ans != Int.MAX_VALUE) {
        println(ans)
    } else {
        println(-1)
    }
}

bit全探索がわかれば、そのまんまなので特に難しいことはないのですが、逆にわからないと意味不明だと思います。

bit全探索についてはこちらのサイトを参考にしました。

Kotlinだと<<がshl、&がandになっているのと、if文の条件に書けるのがBooleanに評価される式だけなのでビットが立っているかどうかの判定を!= 0で判定する必要がある、というのが違いです。

参考書の数だけビットを用意し、ビットが立っていたらその参考書を買うとみなします。何冊買うかは決まっておらず、1冊だけ買うパターンから全部買うパターンまで様々ですが、bit全探索を使うと全て網羅できます。
なので、各パターンについて買うと決まった参考書の分だけ金額とアルゴリズム理解度の合計値を増やし、全ての理解度がX以上になったらその金額が答えの候補となります。最小値が答えなのでmin()を使って小さい方を記録していきます。初回の場合はそれが必ず記録されるように、ansは実際の答えとしてはありえないような十分に大きい値で初期化します。ここではInt.MAX_VALUEで初期化しています。

全探索なので、制約が小さいからこそ成り立つ解法です。 $2^N$ 通り試すことになるため、Nが最大値の12の場合は4096通りです。

0の場合も試していますが、その場合は何も買わないということになり意味がないので、1から始めればよかったかもしれません。

考察と解答

Discussion