PAKEN Programming Camp 2019 Day 1 - Speedrun M: カードはおやつに入りますか?(Are Cards Snacks?)

ちょっとハマったのでメモ。
カードはおやつに入りますか?(Are Cards Snacks?)

問題

N 枚のカードがあり、i 枚目には整数 A[i] が書かれている。square1001 君はカードのうち何枚かを選んで合計 K にしたいので、最小の枚数のカードを除去して邪魔せよ。

解法

愚直にやったら (自分が残すカードの集合, square1001 君がとるカードの集合) の全探索で O(3^N) になる。これでは無理なので高速化を行う。
ある集合 S に対して、「S の部分集合であって、和をとると K になるものの個数」が高速に求めたい気分になるので、dp[S] = (S の和が K なら 1, そうでなければ 0) とした配列 dp に対して高速ゼータ変換を行えばよい。

登場する典型

高速ゼータ変換

実装上の注意点

なし

提出:
https://onlinejudge.u-aizu.ac.jp/beta/review.html#PakenCamp19Day1/4077478
(Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: i64,
        a: [i64; n],
    }
    let mut dp = vec![0; 1 << n];
    for bits in 0..1 << n {
        let mut sum = 0;
        for i in 0..n {
            if (bits & 1 << i) != 0 {
                sum += a[i];
            }
        }
        dp[bits] = if sum == k { 1 } else { 0 };
    }
    for i in 0..n {
        for bits in 0..1 << n {
            if (bits & 1 << i) != 0 {
                continue;
            }
            dp[bits | 1 << i] += dp[bits];
        }
    }
    let mut mi = n;
    for bits in 0usize..1 << n {
        let bc = n - bits.count_ones() as usize;
        if dp[bits] == 0 {
            mi = min(mi, bc);
        }
    }
    puts!("{}\n", mi);
}

まとめ

O(3^N) で解きたくなったら高速ゼータ変換を疑うのが良いかもとは思った。(過適合か…?)