結果

問題 No.15 カタログショッピング
コンテスト
ユーザー なお
提出日時 2014-10-24 17:58:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 2,105 bytes
コンパイル時間 1,039 ms
コンパイル使用メモリ 80,868 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 13:26:39
合計ジャッジ時間 1,762 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 想定解法: 半分全列挙(蟻本2版p147)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

int main(){
    int N, SUM, P[32];
    cin >> N >> SUM;
    if(N < 1 || N > 31 || SUM < 1 || SUM > 310000000){ cerr << "error" << endl; return 1; }
    REP(i,N){
        cin >> P[i];
        if(P[i] > 10000000){ cerr << "error" << endl; return 1; }
    }

    int L = N/2, R = N - L;
    vector<pair<int,int> > list_L, list_R;

    // 前半の組み合わせを全列挙
    list_L.push_back(make_pair(0,0));
    REP(i,L){
        int size = list_L.size();
        REP(j,size){
            auto &v = list_L[j];
            list_L.push_back(make_pair(v.first + P[i], v.second|(1<<i)));
        }
    }

    // 後半の組み合わせを全列挙
    list_R.push_back(make_pair(0,0));
    REP(i,R){
        int size = list_R.size();
        REP(j,size){
            auto &v = list_R[j];
            list_R.push_back(make_pair(v.first + P[L+i], v.second|(1<<(L+i))));
        }
    }

    // 2分探索するためにソート
    sort(list_R.begin(), list_R.end());

    set< vector<int> > result;
    // 前半の値1個づつに対して後半のリストから(SUM-値)を2分探索
    for(auto &v : list_L){
        auto range = equal_range(list_R.begin(), list_R.end(), make_pair(SUM - v.first, 0),
            [](const pair<int,int> &p1, const pair<int,int> &p2){ return(p1.first < p2.first); }
        );
        // 購入パターン構築
        for(auto it = range.first; it != range.second; ++it){
            int list = it->second | v.second;
            vector<int> rv;
            REP(i,N){
                if(list & (1<<i)) rv.push_back(i+1);
            }
            result.insert(rv);
        }
    }

    // 出力
    for(auto &v : result){
        bool f = false;
        for(auto &w : v){
            if(f) cout << " ";
            cout << w; f = true;
        }
        cout << endl;
    }
    return 0;
}
0