まさかの超典型な半分全列挙！！！(蟻本にもほぼ同じ問題あり！！)

問題へのリンク

問題概要

$N$ 個の正の整数 $A_{1}, \dots, A_{N}$ と、正の整数 $T$ が与えられる。 $N$ 個の整数の中からいくつか選んで総和をとる。その値が $T$ より大きくならない範囲内での、その値の最大値を求めよ。

制約

$1 \le N \le 40$
$1 \le T, A_{i} \le 10^{9}$

考えたこと

$N$ が大きくて $T$ が小さい場合は、いわゆる「部分和問題」で DP すると解ける。今回は $T$ がとても大きいので DP は使えない。そのかわり $N \le 40$ という制約が活かせそうに思える。

まずそもそも、単純に全探索した場合、整数の選び方には $2^{N}$ 通りの選択肢があるので、全部で $O(N2^{N})$ の計算量となる。さすがにこれでは間に合わない。こういうとき、半分全列挙が有効なことがある。

今回で言えば、 $N$ 個の整数を $N/2$ 個ずつに分けることにする。そしてそれぞれについての部分和 (いくつか選んだ総和) を全列挙することは可能である。それぞれ $O(2^{N/2})$ 程度の個数になる。よって問題は次の問題に帰着される。

2 つの数列 (サイズが程度) が与えられる
- $p_{1}, p_{2}, \dots$
- $q_{1}, q_{2}, \dots$
これらから 1 個ずつ要素をとって和をとった値が、 $T$ を超えない範囲での最大値を求めよ

たとえば $a = (1, 3, 4, 6)$ のときは

$p = (0, 1, 3, 4)$
$q = (0, 4, 6, 10)$

となる。帰着された問題は、典型的な二分探索の問題となる。 $p$ の要素 ( $p_{i}$ ) を固定して、

$q_{j} \le T - p_{i}$ を満たす最大の $j$

を二分探索 (lower_bound など) によって求めれば OK。計算量は $O(N2^{N/2})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, deque<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


int main() {
    long long N, T;
    cin >> N >> T;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 後半半分を列挙
    vector<long long> q;
    for (int bit = 0; bit < (1<<(N-N/2)); ++bit) {
        long long sum = 0;
        for (int i = 0; i < N-N/2; ++i) if (bit & (1LL<<i)) sum += A[i+N/2];
        q.push_back(sum);
    }
    sort(q.begin(), q.end());
    q.push_back(1LL<<60);

    // 前半を固定して二分探索    
    long long res = 0;
    for (int bit = 0; bit < (1<<(N/2)); ++bit) {
        long long sum = 0;
        for (int i = 0; i < N/2; ++i) if (bit & (1LL<<i)) sum += A[i];
        if (sum > T) continue;
        auto it = upper_bound(q.begin(), q.end(), T - sum) - q.begin();
        --it;
        chmax(res, sum + q[it]);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 184 F - Programming Contest (水色, 600 点)

問題概要

制約

考えたこと

コード