AOJ 0613 Treasures

問題概要

N 個の財宝が与えられ,それぞれ市場価値 w(i)と貴重度 v(i) が決まっている.
この財宝をAとBで分け合う.どちらも獲得しない財宝があってもよい.
分け合った後のAとBの財宝の市場価値の総和をそれぞれ Wa, Wb とする.
また,分け合った後のAとBの財宝の貴重度の総和を Va, Vb とする.
(Wa - Wb の絶対値) <= D を満たすようにしたとき,Vb - Va を最大化せよ.

・制約
1 <= N <= 30
1 <= w(i), v(i) <= 10^15

解法

w と v がでかいので半分全列挙.各要素は pair であり,first には Wa - Wb, second には Vb - Va を保存しておく.

TLE解(?)

半分前列挙した後,片方の集合をソートしておく.この集合を S1 とする.
その集合の各要素の貴重度 V(= p1.second) を,ソートされているこの順番にセグツリに代入しておく.
セグツリでは,各区間の最大値を管理するようにする.

もう片方の集合 S2 の各要素 p2 に対し,-D <= p1.first + p2.first <= D を満たすような集合 S1 の区間は二分探索により求まる.
この区間における S1 の V の最大値は,セグツリにクエリを投げれば分かる.

これを 集合 S2 の各要素にたいして行い,最大値を求める.
計算量は O(3^(N/2) log3^(N/2)) = O(N3^N).

なんだけど,かなりギリギリで,実際8秒制限に対して9秒とかかかってしまう.
定数倍早くしたら通ると思うけど,そんな気力はなかった.ちーん.

間に合う解法

TLE 解では S1 しかソートしてないけど,S2 もソートしておくと良い性質が得られる.

S2 のある要素について調べ終わり,次の要素について調べるときを考える.
すると,S1 のなかの条件を満たす区間は,右にずれる以外ありえないことが(少し考えれば)わかる.
なので,しゃくとり法(スライド最小値?)の要領でやれば良い.

オーダーは変わらないけど,遅いのはソート部分だけなので,セグツリ使うよりは遥かに速い.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<ll, ll>;

constexpr ll INF = 1e18;

void dfs(int i, int const last, vector<P>& res, vector<P> const& input, ll diff, ll val) {
    if(i == last) {
        res.emplace_back(diff, val);
        return;
    }
    dfs(i+1, last, res, input, diff-input[i].first, val-input[i].second);
    dfs(i+1, last, res, input, diff, val);
    dfs(i+1, last, res, input, diff+input[i].first, val+input[i].second);
}

int main() {
    int N;
    ll D;
    cin >> N >> D;

    vector<P> input(N);
    for(int i=0; i<N; ++i) {
        cin >> input[i].first >> input[i].second;
    }

    int N1 = N/2;
    vector<P> v1, v2;
    v1.reserve((int)pow(3, N1));
    v2.reserve((int)pow(3, N-N1));
    dfs(0, N1, v1, input, 0, 0);
    dfs(N1, N, v2, input, 0, 0);
    sort(v1.rbegin(), v1.rend());
    sort(v2.begin(), v2.end());

    ll ans = -INF;
    int t = 0;
    deque<P> deq;
    for(int i=0; i<v1.size(); ++i) {
        while(t < v2.size() && v2[t].first + v1[i].first <= D) {
            while(!deq.empty() && deq.back().second <= v2[t].second) {
                deq.pop_back();
            }
            deq.push_back(v2[t]);
            ++t;
        }
        while(!deq.empty() && deq.front().first + v1[i].first < -D) {
            deq.pop_front();
        }
        if(!deq.empty()) {
            ans = max(ans, v1[i].second + deq.front().second);
        }
    }
    cout << ans << endl;
}