Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

競プロ典型 90 問 037 - Don't Leave the Spice 解説

なんか面白い解法を見つけたので共有します。真に計算量が良い別の解法がある*1ので、そういうのを期待している人はブラウザバックです。

問題概要


問題文(AtCoder)
が十分簡潔なので, こちらを読みましょう。

考察

各調味料の量は、[L_i, R_i]の任意の実数を取りうるが、L_i, R_i以外の量(以下中途半端な量と言う)となる調味料は高々1つとして良いことが証明できる。これは、もし最適な取り方に中途半端な量の調味料が2つあれば、片方を減らし、片方を増やすことで、どちらかをL_i, R_iのいずれかに寄せることができるため、これを繰り返すことで、高々1つとして良いことが証明できる。
よって、中途半端な量となる調味料を固定することで、ナップサックDPの要領で、i番目以外の調味料を使って、合計の量がwのときの最大価値を求めることができる。例えばN番目を中途半端な量とすると

\mathrm{DP}_{i,w} = (i番目までの調味料で, 合計量wとした時の, 価値の最大値)

とすればDP可能である。ただし、これは1回のDPにO(NW)かかり、N回DPを行うため、O(N^2W)であり、定数倍改善の鬼でも通すのは困難である。*2

ここで、この複数回行うDPはかなり無駄があることに注目する。例えば、中途半端な量となる調味料がN番目の時と、N-1番目の時は、ほとんど計算が一致している。さらに、DPする順番は入れ替えても問題がないことにも注意する。ここで

\mathrm{DP}_{l,r,w} = ([l,r)以外番目の調味料で, 合計量をwとした時の, 価値の最大値)

と定める。すると、l\lt m\lt rに対して、\mathrm{DP}_{l,r,*}から\mathrm{DP}_{l,m,*}及び\mathrm{DP}_{m,r,*}O( (r-l)W)で求めることができる*3。最終的に求めたいのは0\leq i\lt Nに対して\mathrm{DP}_{i,i+1,*}を求めたい*4が、[0,n)->[0,n/2), [n/2,n)などのように順番に求めていけば、O(NW\log N)で求めたいものが求められる。

実装

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

inline bool chmax(ll&x,ll y)
{
    if(x<y){
        x=y;
        return true;
    }
    return false;
}

int main()
{
    int W, N;
    cin >> W >> N;
    vector<int> L(N), R(N);
    vector<ll> V(N);
    for(int i{}; i < N; ++i)
        cin >> L[i] >> R[i] >> V[i];
    auto op = [&](vector<ll> &v, int i){
        for(int j{W}; j >= L[i]; --j){
            chmax(v[j], v[j - L[i]] + V[i]);
            if(j >= R[i])
                chmax(v[j], v[j - R[i]] + V[i]);
        }
    };
    struct q{
        int l, r;
        vector<ll> v;
    };
    stack<q> st;
    {
        vector<ll> v(W + 1, LLONG_MIN);
        v[0] = 0;
        st.push(q{0, N, v});
    }
    ll ans{};
    while(!st.empty()){
        auto [l, r, v] = st.top();
        st.pop();
        if(r == l+1){
            for(int i{W-R[l]}; i <= W-L[l]; ++i)
                chmax(ans, v[i] + V[l]);
            continue;
        }
        int m = (l+r) / 2;
        auto vl = v, vr = v;
        for(int i{l}; i < m; ++i) op(vr, i);
        for(int i{m}; i < r; ++i) op(vl, i);
        st.push(q{l, m, vl});
        st.push(q{m, r, vr});
    }
    cout << (ans ? ans : -1) << endl;
}

提出*5

まとめ

これ、有名テクだったりする???俺は知らない。最初平方分割しようとしたんだけど、平方分割できるときは結構セグ木ライクにできることが多いので、試しに考えたら生えた。最初価値がグラム単価だと誤読して生えた(ほぼ同様に解ける)んですが、O(NW)解でもちょっと変形してやれば簡単に解けちゃうんですよね。*6価値が凸関数で与えられるとき*7とかは、この問題じゃないと解けないかな〜〜〜。*8実装がそこそこ綺麗にかけたので満足です。

追記


実は左右から累積するだけでO(NW)で解ける。左右からやるとマージする必要があるからO(NW^2)かかってしまうと思っていたんですが、最後に律儀にマージしなくても答えが導けるので、そんなことはないんですね〜。賢くてびっくりしてしまった。まあこの記事は元々計算量が良い記事というよりは、考え方が面白いよねーってだけなので、まあ別にいいんですが。

*1:具体的には自分の解法は\Theta(NW\log N)で、\Theta(NW)の解法が存在します

*2:O(NW^2)よりは希望がありそう

*3:普通にDPして伸ばせば良い

*4:いつの間にか0-indexに

*5:コンテスト中は私しか見れない

*6:公式解説のセグ木パートをスライド最大値に変更したものが、O(NW)解ですが、スライド最大値に自分の価値-自分の重み*単価みたいのを突っ込んでやれば、同様に解けます。

*7:元問題は定数、誤読版は1次関数なのでともに凸関数

*8:凸であることは最初の中途半端な量が高々1つってところで使います。 ところで


スポンサードリンク