😎

ABC104 C - All Greenのメモ

2023/03/19に公開

AtCoder

競プロ

tech

再帰の練習をしていて、教材の中で練習問題として挙げられていた問題です。解けなかったので解説ACしました。

考察

よく見たら水diffの問題だったのですが最初はそれを知らず、たぶん全探索で解けるような問題だろうと思って再帰で全探索する実装をしました。

各難易度ごとに何問解くかを決めてそれぞれの場合の得点を計算していくのを全て愚直に調べるというガチの全探索です。
（一応、得点が既に条件を満たしていて明らかにそれ以上探索しなくてもいい場合は切り上げていますが、最後になるまで条件を満たさないテストケースがあるはずなので意味ないですね…）

難易度の種類が固定ならfor文をその数だけネストすればいいですが、可変なのでそうもいきません。
$D$ が1の場合は1重ループ、 $D$ が2の場合は2重ループ、...と場合分けしていけばできなくもないですが、というかやっている人見たことありますが、私はやりたくないので再帰でやっています。（便利！）

import kotlin.math.min

fun main() {
    val (d, g) = readLine()!!.split(" ").map { it.toInt() }
    val pc = listOf(0 to 0) + List(d) {
        val (p, c) = readLine()!!.split(" ").map { it.toInt() }
        p to c
    }

    rec(d, g, pc, mutableListOf(), 1)

    println(ans)
}

var ans = Int.MAX_VALUE

@OptIn(ExperimentalStdlibApi::class)
fun rec(d: Int, g: Int, pc: List<Pair<Int, Int>>, list: MutableList<Int>, index: Int): Boolean {
    if(list.size == d) {
        var count = 0
        var score = 0
        for(i in 1..d) {
            count += list[i-1]
            score += list[i-1] * (100 * i)
            if(list[i-1] == pc[i].first) {
                score += pc[i].second
            }
        }
        if(score >= g) {
            ans = min(ans, count)
            return true
        }
        return false
    }

    for(i in 0 .. pc[index].first) {
        list.add(i)
        if(rec(d, g, pc, list, index + 1)) {
            list.removeLast()
            break
        }
        list.removeLast()
    }
    return false
}

まあご覧の通り、これはTLEになります。気づくのに時間がかかったのですが、これだと各難易度の問題の個数が最大101個（0の場合もある）、難易度の種類が最大10個なので、最大だと $101 ^ {10}$ 通りです。そりゃ間に合うわけがなかったです……こういう計算量の見積もりをちゃんとやらないからダメなんですよねぇ。

解決方法は全然わからなかったのでここで解説を見ます。

解説を見て

ネットで見ているとDPを使った解法をよく見かけましたが、公式の解説動画ではDPを使わない解法が紹介されていました。

まず、仮にコンプリートボーナスがなかったのであれば、これは非常に簡単な問題となります。その場合は単に難易度が高い（解いた場合の得点が高い）問題から解いていくだけなので。しかし実際にはコンプリートボーナスがあり、それによって難易度が低い問題を優先して解いてコンプリートボーナスを得たほうが効率がいいかもしれない可能性が生まれることでこの問題は難しくなっているのだと。
コンプリートボーナスが肝なので、コンプリートボーナスを起点に攻略すればいいという発想です。具体的には、まずコンプリートボーナスの得る得ないのパターンを全探索します。最大10個それぞれについて得る得ないの2通りの状態があるので、 $2 ^ {10}$ 通り（1024通り）です。
それで、それぞれについて得ることにしたボーナスに該当する難易度の問題は全て解いたものとして、解いた問題数とスコアを計算します。（なにしろ全部解かないとコンプリートボーナスは得られないので）
それができたら、あとはコンプリートボーナスがない場合かのように難易度が高い問題から解いていって調べればいいということになります。コンプリートボーナスを得ると決めた分については探索せずに一括で計算できるので計算量を削減できるという感じですかね。なるほど、天才ですね…
これなら $1024 \times 1000$ 通りよりも少ないくらいなので計算量としても全く問題なし。

コンプリートボーナスの全探索についてはbit全探索でもできますが、今回は再帰の練習がもともとの目的なので再帰でやっています。
（というか慣れたら再帰のほうが楽のような…）

実装上の注意点としては、得ることに決めたコンプリートボーナスを計算し終わった時点で条件を満たす可能性があるのでその場合の考慮も入れるのと、コンプリートボーナスの分を既に計算した難易度の問題を再度探索しないようにする、くらいですかね。

import kotlin.math.min

fun main() {
    val (d, g) = readLine()!!.split(" ").map { it.toInt() }
    val pc = List(d) {
        val (p, c) = readLine()!!.split(" ").map { it.toInt() }
        p to c
    }
    val p = pc.map { it.first }
    val c = pc.map { it.second }

    rec(d, g, p, c, emptyList())

    println(ans)
}

var ans = Int.MAX_VALUE

fun rec(d: Int, g: Int, p: List<Int>, c: List<Int>, list: List<Int>) {
    if(list.size == d) {
        var count = 0
        var score = 0

        for(i in 0 until d) {
            val m = (i + 1) * 100

            if(list[i] != 0) {
                count += p[i]
                score += p[i] * m + list[i]
            }
        }
        if(score >= g) {
            ans = min(ans, count)
            return
        }

        for(i in d - 1 downTo 0) {
            if(list[i] != 0) {
                continue
            }

            for(j in 0 until p[i]) {
                score += (i + 1) * 100
                count++
                if(j == p[i] - 1) {
                    score += c[i]
                }

                if(score >= g) {
                    ans = min(ans, count)
                    return
                }
            }
        }

        return
    }
    rec(d, g, p, c, list + listOf(c[list.size]))
    rec(d, g, p, c, list + listOf(0))
}

感想

わからない問題がある時、この問題はどのような要素によって難しくなっているのか、その要素による影響はどのようにすれば排除して考えられるのか、というのは汎用的に使えそうな考え方ですね。覚えておきます。
頭が柔らかい人であればすっと思いつくのかもしれないですが、私のような頭がガチガチに硬い人間の場合は、こういう場合はこう考える、みたいな思考パターンを多く記憶していくしかないのだろうなという気がします。

（執筆時間: 52分26秒）

考察

解説を見て

感想

Discussion