スライド最小値の練習

類題とか

問題概要

$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;
}

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

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

JOI 予選 2015 F - 財宝 (AOJ 0613, 難易度 8)

問題概要

制約

考えたこと