高橋くんは $N$ 個の財宝を持っていて,財宝 $i$ は $A_i$ 円で売れる.
青木くんは $N$ 個の商品を売り出していて,商品 $i$ は $C_i$ 円で打っていて価値は $V_i$ である.
高橋くんの最初の所持金は $0$ であり,以下の通りに行動する.
高橋くんは買う商品の価値の総和をできるだけ高くするように行動する.
逆に青木くんはできるだけ低くなるように行動する.
買う商品の価値の総和を求める問題.
まず,前計算として,最後に購入するときの高橋くんの最適な行動を動的計画法で求める.
つまり,
dp2[k][mask] = k個の財宝を売却したお金で,maskの商品が売り出されているときに買うことができる商品の価値の総和の最大値
を計算しておく.ただし,maskは販売中の商品の集合を表す.
これは,kごとに別々に計算し,全ての売り出し中の商品が購入できるなら
dp2[k][mask] = 売り出し中の商品の価値の総和
となるし,そうでなければ,必ず1つの商品を購入しないので,
dp2[k][mask] = max(dp2[k][maskから1つの商品を取り除いたもの])
となる.これは,時間計算量 $O(N^2 2^N)$ で計算可能.
後は,高橋くんのいつ売却を止めるか,および,青木くんの行動を動的計画法で求める.つまり,
dp[mask] = 販売商品の集合がmaskのときに以降両者最適に行動したときの高橋くんが購入する商品の価値の総和
を計算する.これは,maskにおいて販売停止した商品数がkのとき
dp[mask] = max(dp2[k][mask], min(dp[maskから1つの商品を取り除いたもの]))
で計算可能.maxは高橋くんの行動に関して,minは青木くんの行動に関して最適な選択をした場合に対応していることに注意.
合計で時間計算量は $O(N^2 2^N)$ 程度になる.
dp2を前計算せず,毎回残されている商品に対して,買う部分集合をすべてチェックする $O(N^3)$ でも通る.
C++に変換後のコードはこちら
int N;
ll X[20], C[20], V[20];
ll dp[3d5];
ll sumX[20];
ll sumC[3d5], sumV[3d5];
ll dp2[20][3d5];
int bt[3d5];
ll solve(int mask, int cnt){
int i;
ll res = 0, tmp;
if(dp[mask] >= 0) return dp[mask];
res = dp2[cnt][mask];
if(mask){
tmp = ll_inf;
rep(i,N) if(mask&1<<i){
tmp <?= solve(mask^(1<<i), cnt+1);
}
res >?= tmp;
}
return dp[mask] = res;
}
{
int i, j, k;
ll res;
rd(N,X(N),C(N),V(N));
rep(i,N) bt[1<<i] = i;
rep(i,1,1<<N){
j = i&(-i);
sumC[i] = sumC[i^j] + C[bt[j]];
sumV[i] = sumV[i^j] + V[bt[j]];
}
sumX[0] = 0;
rep(i,N) sumX[i+1] = sumX[i] + X[i];
rep(k,N+1){
rep(i,1<<N){
if(sumC[i] <= sumX[k]){
dp2[k][i] = sumV[i];
continue;
}
dp2[k][i] = 0;
rep(j,N) if(i&1<<j){
dp2[k][i] >?= dp2[k][i^(1<<j)];
}
}
}
rep(i,1<<N) dp[i] = -1;
res = solve((1<<N)-1, 0);
wt(res);
}
Current time: 2024年03月28日18時18分16秒
Last modified: 2018年02月12日17時55分07秒 (by laycrs)
Tags: Competitive_Programming AtCoder yahoo-procon2018-qual
トップページに戻る
Logged in as: unknown user (not login)