😺

ABC 322 E - Product Developmentのメモ

2023/10/04に公開

AtCoder

競プロ

tech

先日出たABCで解けなかった問題です。

考察

各開発案はそれぞれ「実行する」「実行しない」の2つの状態を持つので、bit全探索などを使って全ての組み合わせを試せば一応解けます。しかし、最大で $2^{100}$ 通りもあるので間に合いません。そういう系統の問題はだいたいDPで解けるイメージがあり、この問題もそうだろうと思いました。
ただ、パラメータが $K$ 個あるというのが今まで個人的に見てきたDPの問題とは違うところです。これが1つだけなら過去解いた問題と同じ解法が適用できるのですが…
5次元配列とか使えば解けそうとは思いましたが、データの状態がイメージできなくて書けず。バラバラにやったらどうなのだろうと思ってやってみましたが、それだと各パラメータについての最小コストはわかるのですが、それぞれがどの開発案を採用したのかが同じとは限りません。この方法だとどの開発案を採用した結果その最小値になったのかわからないので、最終的な答えを求めることはできません。ということでコンテスト中は解けずじまいでした…

解説を見て

まあ解説といってもコンテスト終了直後は以下のシンプルな解説文しかなく、読んでもピンときませんでした。

そこでコンテスト後のTwitter（X）のTLで見かけた「bitDP」という用語でググったりとかしていました。
最初に出てきた以下のサイトで
https://algo-logic.info/bit-dp/#

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。

という文がありました。それ以降ちゃんと読んでいないのですが、なんかこれだけで一気にわかったような気になりました。
解説を読んだだけだと、 $P + 1$ 進数とかmapとか何の話なのかサッパリでしたが、上記と組み合わせて考えると、要するに複数の情報（ $K$ 個のパラメーター）を一つの情報としてまとめてしまい、それを添え字とすればいいのかと。複数の値にまとめるやり方として $P + 1$ 進数を使えば数値になるので普通に配列の添え字として使えますし、文字列とかにしてmapを使ってもいい。そういう話かーー
「 $K$ 個のパラメーター」に惑わされていましたが、一つの開発案を選んだらその $K$ 個のパラメーターは全部変動するし、どのように変動するのかという情報も与えられているので、「 $K$ 個のパラメーター」を一つにまとめてしまえば、あとは今まで見てきたDPと何も変わらないじゃないかという話でした。

つまり開発案の種類が行、パラメーターの状態（をまとめたもの）を列とする二次元のDP表を埋めるだけ。値として持つのはもちろんコストです。
解説文にあった

P を超えたステータスは P で打ち切ってもよいため途中でのステータスの種類は実質 $O((P+1)^K)$ 通りしかないことに注目します。

の意味もやっとわかりました。この値が列となり、それを全探索するので、これがバカでかい値になると成り立たないので。
$P$ も $K$ も最大値は5なので $O((P+1)^K)$ の最大値は6進数の5桁で55555、10進数だと7776です。これなら $N$ が最大値の100でも余裕です。

実装

コメントで補足しました。パラメータは $(P + 1)$ 進数を0埋めしたStringにしました。これをMapで扱います。各行について00000～55555（ $P$ も $K$ も最大値の場合）を見て、値があったら配ります。dp[0]["00000"] にはDPの種として0を入れておきます。

import kotlin.math.min
import kotlin.math.pow

fun main() {
    val (n, k, p) = readln().split(" ").map { it.toInt() }

    val c = mutableListOf<Long>()
    val a = mutableListOf<IntArray>()
    repeat(n) {
        val ca = readln().split(" ").map { it.toInt() }
        c.add(ca.first().toLong())
        a.add(ca.subList(1, ca.size).toIntArray())
    }

    // パラメータとしてあり得る値の最大値（最大で6進数の55555）
    val limit = (p + 1).toDouble().pow(k).toInt() - 1
    
    // 行が開発案の種類、列がパラメータの状態、値がコスト
    val dp = Array(n + 1) { mutableMapOf<String, Long>() }
    // 値があったら次の行に渡す（配る）ようにする
    // 0の位置から配ることで、初めて採用する開発案がその時注目している開発案である場合の遷移を実現
    dp[0]["0".repeat(k)] = 0

    // 最終行のnからは配らないのでnまでは見ない
    for(i in 0 until  n) {
        for(j in 0 ..  limit) {
            // (P + 1)進数の0埋めで00000から55555まで見る
            // 00001, 00002,... ではなく10000, 20000,... のようになるほうがAと位置情報が一致するのでやりやすい（そのためのreversed）
            val current = j.toString(p + 1).padStart(k, '0').reversed()

            // 値がなかったら、その位置には到達し得ないのでそれ以上配らない
            if(dp[i][current] == null) {
                continue
            }

            // その開発案を採用しない場合の表現として、真下に配る（既に値があった場合、大きい値で上書きしないようにminをとる）
            dp[i+1][current] = min(dp[i+1][current] ?: Long.MAX_VALUE, dp[i][current]!!)

            // その開発案を採用する場合、現在のパラメータに足したパラメータに対応する位置に値を書き込む
            // これも既に値があるかもしれないのでminをとる
            val next = add(current, a[i], p)
            dp[i+1][next] = min(dp[i+1][next] ?: Long.MAX_VALUE, dp[i][current]!! + c[i])
        }
    }

    // 全桁でp以上の値があったらそれが答え
    println(dp[n][p.toString().repeat(k)] ?: -1)
}

private fun add(base: String, a: IntArray, p: Int): String {
    // minをとることで、pより大きい値にならないようにする（p以上であればいいので、それより大きい値を扱う必要がない）
    return base.indices.joinToString("") { min(p, base[it].digitToInt() + a[it]).toString() }
}

まあ、解法がわかった後はサラッと実装できたかのように言っていますが、実際にはけっこう実装に苦労して、しかも1回ペナりました。典型的なDPでもまだ実装にはけっこう苦労します。解法がわからないだけでなく、わかっても実装に苦労するとは、ほんとにまだまだだなあという感じです。
（執筆時間: 51分34秒）

考察

解説を見て

実装

Discussion