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

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

AOJ 0613 財宝 (JOI 2014 予選 F)

スライド最小値の練習

問題へのリンク

問題概要

 N 個のアイテムがって、それぞれ市場価値  d_i と貴重度  v_i が与えられる。

今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテムを取ることはできず、2 人ともとらないアイテムがあってもよい。

これら  3^{N} 通りのアイテムのとられかたのうち、A さんの獲得市場価値と、B さんの獲得市場価値の差が  D 以下であるものについて、B さんの獲得貴重度から A さんの獲得貴重度を引いた値の最大値を求めよ。

制約

  •  1 \le N \le 30

考えたこと

一目見て半分全列挙なのだが、なかなかこういうの慣れなくて重たい。アイテムを半分ずつに分けてそれぞれについて、

  • (B さんの市場価値 - A さんの市場価値, B さんの貴重度 - A さんの貴重度)

としてありうるものを列挙していく (それぞれ  L, R とする)。これには  O(3^{\frac{N}{2}}) の計算時間を要する。さらに

  •  L については降順にソート
  •  R については昇順にソート

しておく。 L も普通にソートしてもいいのだが、後先わかりやすくするために降順にソートしている。ここで、問題は


各 L の要素  d_{L}, v_{L} に対して、

  • R の要素  d_{R}, v_{R} のうち、 d_{R} - d - D 以上  - d + D 以下

であるもののうち、 v_{R} が最大のものをとってくる


という問題になる。これは実はスライド最大値問題になっているので deque を有効に活用することができる。

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;


// slide min
template<class VAL, class TIME> struct SlideMin {
    const VAL INF = 1LL<<60; // to be set appropriately
    const TIME nul = -1; // to be set appropriately
        
    deque<pair<VAL, TIME> > deq;
    SlideMin()  { }

    // get minimum
    pair<VAL, TIME> get() {
        if (deq.empty()) return make_pair(INF, nul);
        return deq.front();
    }

    // push (v, t), "t is non-decreasing" is necessary
    void push(VAL v, TIME t) {
        while (!deq.empty() && deq.back().first >= v) deq.pop_back();
        deq.emplace_back(v, t);
    }

    // pop "< t", "t it non-decreasing" is necessary
    void pop(TIME t) {
        while (!deq.empty() && deq.front().second < t) deq.pop_front();
    }
};



vector<long long> X, Y;
void rec(int i, int last, long long x, long long y, vector<pll> &v) {
    if (i == last) {
        v.push_back(pll(x, y));
        return;
    }
    rec(i + 1, last, x, y, v);
    rec(i + 1, last, x + X[i], y - Y[i], v);
    rec(i + 1, last, x - X[i], y + Y[i], v);
}

int main() {
    int N; long long D; cin >> N >> D;
    X.resize(N); Y.resize(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];
    vector<pll> L, R;
    rec(0, N/2, 0, 0, L);
    rec(N/2, N, 0, 0, R);
    sort(L.begin(), L.end(), greater<pll>());
    sort(R.begin(), R.end());

    long long res = 0;
    SlideMin<long long, long long> sm;
    int pos = 0;
    for (auto it : L) {
        // push
        while (pos < R.size() && R[pos].first <= -it.first + D) {
            sm.push(-R[pos].second, R[pos].first);
            ++pos;
        }
        
        // pop
        sm.pop(-it.first - D);

        // get
        long long minv = -sm.get().first;
        res = max(res, it.second + minv);
    }
    cout << res << endl;
}