結果

問題 No.15 カタログショッピング
ユーザー なおなお
提出日時 2014-10-24 17:58:33
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 2,105 bytes
コンパイル時間 1,442 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 17:37:14
合計ジャッジ時間 1,490 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 10 ms
6,940 KB
testcase_06 AC 12 ms
6,940 KB
testcase_07 AC 12 ms
6,940 KB
testcase_08 AC 13 ms
6,940 KB
testcase_09 AC 12 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 想定解法: 半分全列挙(蟻本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