CODE FESTIVAL 2018 Final I - Homework

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の冪乗系コストの問題は、たまに見ると面白い。