Yukicoder015 カタログショッピング

問題概要

$N$個の商品が与えれる。それぞれの値段は$P[i]$円である。 今$S$円だけ買ったことは覚えているので、ちょうど$S$円になる組合せを全て求めてその商品番号を辞書順最小で出力せよ。

$N\leqq31$、$S\leqq3.1*10^8$、$P[i]\leqq10^7$

yukicoder015

解法

Nが大きいので、$O(2^N)$は厳しそう。 そこで、半分前列挙をする。 IDの出力が面倒で、辞書順最小とするためには2進数のbitを反転して管理する必要がある。 これ、$a[i]$をreverseするともっとやるだけっぽそう…

計算量:$O(2^{2/N}log(2^{2/N}))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    using VL = vector<LL>;        using VVL = vector<VL>;
    
    #define ALL(a)  begin((a)),end((a))
    #define RALL(a) (a).rbegin(), (a).rend()
    #define SZ(a) int((a).size())
    #define SORT(c) sort(ALL((c)))
    #define RSORT(c) sort(RALL((c)))
    #define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N, S;
    
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> S;
        VL a(N);
    
        FOR(i, 0, N) {
            cin >> a[i];
        }
        vector<PLL>v;
        int n1 = N / 2;
        FOR(i, 0, 1 << n1) {
            LL sum = 0;
            LL bit = 0;
            FOR(j, 0, n1) {
                if (i & (1 << j)) {
                    sum += a[j];
                    bit += 1LL << (N - j);
                }
            }
            v.push_back(PLL(sum, bit));
        }
        SORT(v);
        int n2 = N - n1;
        VL ans;
        FOR(i, 0, 1 << n2) {
            LL sum = 0;
            LL bit = 0;
            FOR(j, 0, n2) {
                if (i& (1 << j)) {
                    sum += a[n1 + j];
                    bit += 1 << (N - (n1 + j));
                }
            }
    
            auto x = lower_bound(ALL(v), PLL(S - sum, 0LL));
            auto y = lower_bound(ALL(v), PLL(S - sum, 1LL << 32));
            for (; x != y; x++) {
                if (x->first + sum == S) {
                    ans.push_back(x->second | bit);
                }
            }
        }
        RSORT(ans);
        FOR(i, 0, SZ(ans)) {
            int out = 0;
            FOR(k, 0, N) {
                if (ans[i] & (1LL << (N - k))) {
                    if (out)cout << " ";
                    out = 1;
                    cout << k + 1;
                }
            }
            if (out)cout << endl;
        }
    
        return 0;
    }