【ABC184】F - Programming Contest

atcoder.jp

解法

全探索しようとするとO(2^N)になり、制約が N ≦ 40 なのでこれでは間に合わない。

そこで、半分全列挙というテクニック使ってO(2^N/2)で解くことを考える。

N個の問題を2つのグループに分けて、それぞれのグループごとに問題の選び方を全探索する。
それぞれ解くのにかかった時間を配列に保持しておく。
それから、片方の配列は昇順にソートしておく。
ソートしていない方の配列をt1、ソートしている方をt2と呼ぶことにする。

次に、t1を前から順に見ていくことにする。 前からi番目の要素をt1[i]と表現する。
ここで二分探索によって、T-t1[i]以下で最大のt2の要素は何かという問題を解くことができる。
答えはこの問題を解くことによって得られた解の最大値になる。

実装

前半、後半ともに先に全探索してしまったが、前半だけ全探索してソートしておき、後半部分を全探索しながら二分探索という実装方法の方が簡単な気がする。

void solve(long long N, long long T, std::vector<long long> A){
    // N/2を繰り上げたもの
    int n = myceil(N, 2LL);

    // t1 = sm1, t2 = sm2
    // sm1: 前半、sm2: 後半
    vector<ll> sm1, sm2;
    // bit全探索で問題の選び方を全探索
    // Nが奇数の可能性があるため、if文を使って結果を調整している
    for (int bit = 0; bit < (1<<n); bit++) {
        ll cur1 = 0;
        ll cur2 = 0;
        for (int i = 0; i < n; i++) {
            if (bit & (1<<i)) {
                if (N/2 == n || i != n-1) cur1 += A[i];
                cur2 += A[N/2+i];
            }
        }

        if (N/2 == n || bit <= (1<<(n-1))) sm1.push_back(cur1);
        sm2.push_back(cur2);
    }

    sort(all(sm2)); // sm2を昇順ソート

    ll mx = 0;
    REP (i, sm1.size()) {
        // 二分探索でT-sm[i]以下で最大のsm2の要素を探す
        auto iter = upper_bound(all(sm2), T-sm1[i]) - 1;
        ll cur = sm1[i]+*iter;
        if (cur <= T) chmax(mx, cur);
    }

    cout << mx << endl; // 出力
}