AtCoder ABC 142 E - Get Everything 解説AC (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。解説ACですが記事にすることはできそうでした。

問題

これも一つのbitDPではありそうですが、特殊なケースになると思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type key struct {
    cost int
    open int
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    pattern := 1 << uint(n)
    keys := make([]key, m)
    for mi := 0; mi < m; mi++ {
        a, b := nextInt(), nextInt()
        open := 0
        for bi := 0; bi < b; bi++ {
            c := nextInt()
            open = open | (1 << uint(c-1))
        }
        keys[mi] = key{a, open}
    }

    dp := make([][]int, m+1)
    dp[0] = make([]int, pattern)
    // dp[0][0] = 0
    for pi := 1; pi < pattern; pi++ {
        dp[0][pi] = INF
    }

    for mi := 0; mi < m; mi++ {
        dp[mi+1] = make([]int, pattern)
        copy(dp[mi+1], dp[mi])
        for pi := 0; pi < pattern; pi++ {
            pnext := pi | keys[mi].open
            if dp[mi][pi]+keys[mi].cost < dp[mi+1][pnext] {
                dp[mi+1][pnext] = dp[mi][pi] + keys[mi].cost
            }
        }
    }

    switch {
    case dp[m][pattern-1] < INF:
        fmt.Println(dp[m][pattern-1])
    default:
        fmt.Println(-1)
    }
}

まず計算量の見通しを立てる必要があります。まず $N$ について考えると、それぞれの宝箱を開けられるかどうかを考えることになるので、 $O(2^N)$ または $O(2^NN)$ 辺りになりそうです。なので全体の計算量は $O(2^NM(\times N))$ 辺りになると考えられます。

ここでbitDPで解くことを考えてみます。この問題をbitDPで解くということは、以下のように箱に対するDPに帰着されるということになります。

$N_0$ 個の宝箱を開ける場合の組み合わせそれぞれに対する最小費用を求める。
1.の結果を利用して $N_0+1$ 個の宝箱を開ける場合の組み合わせそれぞれに対する最小費用を求めることができる。

しかし、このようなアルゴリズムに帰着させることができないことが示せます。例えば入力例1をアレンジした以下の入力に対する解を考えます。

この場合、 $1$ 個の宝箱を開ける場合の最小費用は箱 $1,2$ それぞれに対して $10,15$ となりますが、 $2$ 個の宝箱を開ける場合の最小費用は $10+15=25$ ではなく、 $3$ 番目の鍵のみ購入する $20$ となります。

つまり、箱に対してDPを適用することはできません。今回はここで詰まってしまい解説ACすることとなりました。

結論としては、箱ではなく鍵に対してDPを適用することでこの問題を解くことができます。ナップサック問題の変形として考えると以下のような問題になります。

荷物の価値を鍵の価格、荷物の重さ（容量）を鍵に対応する宝箱の（bitによる）組み合わせに置き換える。
$1,2,\ldots,M_0$ 番目の鍵を用いることができる場合の、開けることができる宝箱の組み合わせとそのときの最小費用を求める。
2.の宝箱の組み合わせと $M_0+1$ 番目の鍵に対応する宝箱の組み合わせの論理和を求めることによって、 $1,2,\ldots,M_0,M_0+1$ 番目の鍵を用いることができる場合の、開けることができる宝箱の組み合わせとそのときの最小費用を求めることができる。
$M$ 個の鍵全てを用いることができる場合の、 $N$ 個全ての宝箱を開けることができる最小費用が最終的な解となる。