Subset POJ 3977

投稿日：2023/01/04 更新日:2023/01/04

POJ

競プロ

問題：http://poj.org/problem?id=3977

問題

絶対値が $10^{15}$ 以下の $N$ 個の整数が与えられる。この中から空でない部分集合の総和の絶対値が最小であるものを見つけてください。解が複数ある場合は要素数が最小の物を求めてください。

総和と要素数をスペース区切りで出力すること。

解法

$N \leqq 35$ なので半分列挙使います。

数列を半分にし、それぞれビット全探索を行い列挙します。左半分を $l$ 、右半分を $r$ とします。全探索を $1$ スタートにしている理由は集合が空になることを阻止するためです。

その後、 $l$ のみ、 $r$ のみの場合での答えを求めています。

次に、 $l$ , $r$ で組み合わせた場合の答えを求めて行きます。 $l$ を固定した時、適切な $r$ の値を二分探索で求めれば良いです。lower_boundで見つけた値と、その一つ手前の値のどちらかが和が最小になる値です。

二分探索する側の $r$ は重複する値がある可能性があるので、同じ値は要素数が最小のものだけ残して置きます。

実装

POJの環境が古く、そのままabsを使ってもlong longに対応してません。そのため、自分であらかじめ実装する必要があります。ただし、実装するとバージョンの違いにより、手元の環境では動かないが、POJ側の環境では動くみたいなことになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

long long abs(long long v){
    if(v < 0){
        return -v;
    }
    return v;
}

void solve(int n){
    vector<long long> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }

    vector<pair<long long, int>> l;
    for(int s = 1;s < 1<<n/2; ++s){
        long long sum = 0;
        int count = 0;
        for(int i = 0;i < n/2; ++i){
            if(s>>i & 1){
                sum += a[i];
                count++;
            }
        }
        l.push_back(make_pair(sum, count));
    }
    vector<pair<long long, int>> r;
    for(int s = 1;s < 1<<(n - n/2); ++s){
        long long sum = 0;
        int count = 0;
        for(int i = 0;i < (n - n/2); ++i){
            if(s>>i & 1){
                sum += a[i+n/2];
                count++;
            }
        }
        r.push_back(make_pair(sum, count));
    }

    pair<long long,int> ans = make_pair((long long)1e18 + 100, 1e9);

    for(int i = 0;i < l.size(); ++i){
        pair<long long, int> tmp = make_pair(abs(l[i].first), l[i].second);
        ans = min(tmp, ans);
    }
    for(int i = 0;i < r.size(); ++i){
        pair<long long, int> tmp = make_pair(abs(r[i].first), r[i].second);
        ans = min(tmp, ans);
    }

    sort(r.begin(), r.end());
    for(int i = 1;i < r.size(); ++i){
        if(r[i].first == r[i-1].first){
            r[i].second = r[i-1].second;
        }
    }
    r.erase(unique(r.begin(), r.end()), r.end());

    for(int i = 0;i < l.size(); ++i){
        vector<pair<long long,int>>::iterator itr =  lower_bound(r.begin(), r.end(), make_pair(-l[i].first, 0));
        for(int k = -1;k <= 0; ++k){
            if(itr+k < r.begin() || itr+k >= r.end())continue;
            long long nsum = abs(l[i].first + (itr+k)->first);
            int ncount = l[i].second + (itr+k)->second;
            pair<long long, int> tmp = make_pair(nsum, ncount);
            ans = min(ans, tmp);
        }
    }

    printf("%lld %d\n", ans.first, ans.second);
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    while(n != 0){
        solve(n);
        cin >> n;
    }
    return 0;
}