F問題は解説を見ないとわからなかったがI問題は自力で解けた。
I - Homework
問題
荷物がN個ある。i番目の荷物はコスト2^A[i]、価値B[i]である。合計価値をK以上にするために必要なコストの合計を求めよ。
制約
- 入力は全て整数
- 1 <= N <= 10^5
- 0 <= A[i] <= 30
- 1 <= B[i] <= 10^9
- 1 <= K <= \sum B[i]
解法
二分探索をすることにして、問題を「合計コストx以下で合計価値をK以上にできるか?」という形に変形する。
ここで、xの偶奇とコスト1の荷物をどうするかに着目しよう。xが奇数であれば、少なくとも1個はコスト1の荷物を取るべきである。またxが偶数であっても奇数であっても、最初に取る荷物以外の荷物は2個ずつ取っていくべきである。これを使うと、xの各ビットを下から見て、立っていたら一番価値の高い荷物を取り、そのあとそれ以外の荷物を2個まとめてコストが2倍の荷物として扱うとよいことがわかる。
これの計算量は、ほとんどの荷物の個数が毎ターン半分になること、最大1個の荷物がそれ以外に次のターンに持ち越されることを考えると、O(N + (ターン数)) = O(N + max A[i])である。
登場する典型
- 二分探索
- 1, 2, 2^2, ...という等比数列の典型パターン
- 今回は下位ビットに着目するといけた
実装上の注意点
- 二分探索の範囲
- 上限はN * 2^30以上にすべき
- 上限に応じてxの大きさも変わるので、ターン数も30ではなくもっと大きくしないといけない
提出: Submission #4325140 - CODE FESTIVAL 2018 Final (Parallel) (Rust)
const B: usize = 31; const C: usize = 50; // x: max time fn can_pack(tbl: &[Vec<i64>], k: i64, x: i64) -> bool { let mut rem = k; let mut cur_bag = tbl[0].clone(); for i in 0..C { cur_bag.sort(); if (x >> i & 1) == 1 && cur_bag.len() >= 1 { rem -= cur_bag.pop().unwrap(); } let mut nxt = vec![]; while let Some(mut fst) = cur_bag.pop() { if let Some(snd) = cur_bag.pop() { fst += snd; } nxt.push(fst); } if i + 1 < B { nxt.extend_from_slice(&&tbl[i + 1]); } cur_bag = nxt; } rem <= 0 } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($format:expr) => (write!(out,$format).unwrap()); ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap()) } input! { n: usize, k: i64, ab: [(usize, i64); n], } let mut tbl = vec![vec![]; B]; for (a, b) in ab { tbl[a].push(b); } let mut pass = 1 << C; let mut fail = 0; while pass - fail > 1 { let mid = (pass + fail) / 2; if can_pack(&tbl, k, mid) { pass = mid; } else { fail = mid; } } puts!("{}\n", pass); }
まとめ
2の冪乗系コストの問題は、たまに見ると面白い。