• ARC017 C - 無駄なものが嫌いな人 (AtCoder Regular Contest 017 C問題) https://atcoder.jp/contests/arc017/tasks/arc017_3
  • https://atcoder.jp/contests/arc017/submissions/41100114
  • 半分全列挙
  • 2^32 は間に合わないけど 2^16 * 2 なら間に合う
  • 変な分岐を入れているけど 0 の個数も数えているので usize -> i64 にしておけば分岐は不要

use std::collections::HashMap;

use proconio::input;

fn main() {
    input! {
        n: usize,
        x: usize,
        w: [usize; n],
    }

    let mut count1 = HashMap::new();
    for bits in 0..1 << (n / 2) {
        let mut sum = 0_usize;
        for i in 0..n / 2 {
            if (bits >> i) & 1 == 1 {
                sum += w[i];
            }
        }
        *count1.entry(sum).or_insert(0) += 1_usize;
    }

    let mut count2 = HashMap::new();
    for bits in 0..1 << (n - (n / 2)) {
        let mut sum = 0_usize;
        for i in 0..(n - (n / 2)) {
            if (bits >> i) & 1 == 1 {
                sum += w[n / 2 + i];
            }
        }
        *count2.entry(sum).or_insert(0) += 1_usize;
    }

    let mut ans = 0_usize;
    for (sum, c1) in count1 {
        let c2 = match x.cmp(&sum) {
            std::cmp::Ordering::Less => 0_usize,
            std::cmp::Ordering::Equal => 1_usize,
            std::cmp::Ordering::Greater => *count2.get(&(x - sum)).unwrap_or(&0),
        };
        ans += c1 * c2;
    }
    println!("{}", ans);
}

右の唇の下に吹き出物ができている。気になる。

今日のコミット。

• rust-atcoder 1 commit
  • pastbook1 arc017 c
• tsukota 2 commits
  • Change storeEvent and getEvents signatures
  • Fix buildCreateAccount