AtCoder Regular Contest 017 C - 無駄なものが嫌いな人

問題

　整数とが与えられるので、総和がとなるような選び方が何通りあるか求めよ。

解法

　半分全列挙。個の数字のうち前半について組み合わせを全て列挙してそれぞれの和を配列に確保しソートする。後半についても組み合わせを列挙して和を求め、に足りない分を先ほど求めた配列の中から二分探索で探す。計算量はかな？ 正確さはともかく間に合う。

反省

　8分8秒でAC。パッと見で解法が浮かんだし実装も一発でできた。特に問題なし。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X;
    cin >> N >> X;
    vector<ll> w(N);
    for (ll i = 0; i < N; i++) {
        cin >> w[i];
    }

    ll h_n = N / 2;
    ll r_n = N - h_n;

    vector<ll> candidate;
    for (ll i = 0; i < (1 << h_n); i++) {
        ll sum = 0;
        for (ll j = 0; j < h_n; j++) {
            if (i & (1 << j)) {
                sum += w[j];
            }
        }
        candidate.push_back(sum);
    }

    sort(candidate.begin(), candidate.end());

    ll ans = 0;
    for (ll i = 0; i < (1 << r_n); i++) {
        ll sum = 0;
        for (ll j = 0; j < r_n; j++) {
            if (i & (1 << j)) {
                sum += w[j + h_n];
            }
        }

        ll need = X - sum;
        auto s = lower_bound(candidate.begin(), candidate.end(), need);
        auto e = upper_bound(candidate.begin(), candidate.end(), need);

        ans += e - s;
    }

    cout << ans << endl;
}