【Rust】bit全探索を実装する

はじめに

RustでABC125 B - Resaleを解いていて，bit全探索を実装する方法がわからなかったので，こちらにメモを残しておきます．

bit全探索を実装する

bit全探索については，以下の記事が非常にわかりやすいので，こちらをご参照ください．

たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 - Qiita

以下，ABC125 B - Resaleの解答です．
i番目のビットが立っているかどうかは，bit & (1 << i) > 0で調べることができます．

use proconio::{
    input,
    marker::{Bytes, Chars},
};

fn main() {
    input! {
        n: usize,
        v: [i32; n],
        c: [i32; n],
    };

    let mut ans = -1000;

    // 2^n通りの組み合わせを全て検討する
    for bit in 0..(1 << n) {
        // ある組み合わせにおける x - yの値を保持する
        let mut total = 0;

        // j番目のbitが立っているかどうかを確認
        for i in 0..n {
            // bitが立っている場合は，x - yの値に加算する
            if bit & (1 << i) > 0 {
                total += v[i] - c[i];
            }
        }

        if ans < total {
            ans = total;
        }
    }
    println!("{}", ans);
}

参考

• bit全探索 AtCoderでよく見かける書き方 - Qiita
• B - Resale