競プロ典型 90 問 037 - Don't Leave the Spice 解説
なんか面白い解法を見つけたので共有します。真に計算量が良い別の解法がある*1ので、そういうのを期待している人はブラウザバックです。
問題概要
【37 日目】
— E869120@公開アカウント (@e869120) 2021年5月10日
昨日の解説と今日の典型問題です。標準的な難易度となっています。なお、AtCoder ジャッジには 15 時頃に追加される予定です。(入力形式・入出力例は GitHub を参照のこと) #競プロ典型90問 pic.twitter.com/UpvDJT8Efy
問題文(AtCoder)
が十分簡潔なので, こちらを読みましょう。
考察
各調味料の量は、の任意の実数を取りうるが、以外の量(以下中途半端な量と言う)となる調味料は高々1つとして良いことが証明できる。これは、もし最適な取り方に中途半端な量の調味料が2つあれば、片方を減らし、片方を増やすことで、どちらかをのいずれかに寄せることができるため、これを繰り返すことで、高々1つとして良いことが証明できる。
よって、中途半端な量となる調味料を固定することで、ナップサックDPの要領で、番目以外の調味料を使って、合計の量がのときの最大価値を求めることができる。例えば番目を中途半端な量とすると
番目までの調味料で, 合計量とした時の, 価値の最大値)
とすればDP可能である。ただし、これは1回のDPにかかり、回DPを行うため、であり、定数倍改善の鬼でも通すのは困難である。*2
ここで、この複数回行うDPはかなり無駄があることに注目する。例えば、中途半端な量となる調味料が番目の時と、番目の時は、ほとんど計算が一致している。さらに、DPする順番は入れ替えても問題がないことにも注意する。ここで
(以外番目の調味料で, 合計量をとした時の, 価値の最大値)
と定める。すると、に対して、から及びをで求めることができる*3。最終的に求めたいのはに対してを求めたい*4が、->などのように順番に求めていけば、で求めたいものが求められる。
実装
#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; }
まとめ
これ、有名テクだったりする???俺は知らない。最初平方分割しようとしたんだけど、平方分割できるときは結構セグ木ライクにできることが多いので、試しに考えたら生えた。最初価値がグラム単価だと誤読して生えた(ほぼ同様に解ける)んですが、解でもちょっと変形してやれば簡単に解けちゃうんですよね。*6価値が凸関数で与えられるとき*7とかは、この問題じゃないと解けないかな〜〜〜。*8実装がそこそこ綺麗にかけたので満足です。
追記
あれ?
— drogskol (@cureskol) 2021年5月12日
dp1[i][j]:[0,i)で重みjの価値の最大値
dp2[i][j]:[i,n)で重みjの価値の最大値
(ただし使う重みはL,Rだけ)
として、i番目のだけ[L,R]で使うやつは
max_j ( dp1[i][j] + max_{k:[w-j-R,r-j-L]} dp2[i+1][k] )
で、これはjを全部見ながらkはdp2に対する幅R-Lのスライド最大値で出来ないかしら
実は左右から累積するだけでで解ける。左右からやるとマージする必要があるからかかってしまうと思っていたんですが、最後に律儀にマージしなくても答えが導けるので、そんなことはないんですね〜。賢くてびっくりしてしまった。まあこの記事は元々計算量が良い記事というよりは、考え方が面白いよねーってだけなので、まあ別にいいんですが。