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) で解きたくなったら高速ゼータ変換を疑うのが良いかもとは思った。(過適合か…?)