「みんなのプロコン 2018」予選 C問題 - 駆引取引

Source

「みんなのプロコン 2018」予選
問題文

問題概要

高橋くんは $N$ 個の財宝を持っていて,財宝 $i$ は $A_i$ 円で売れる.
青木くんは $N$ 個の商品を売り出していて,商品 $i$ は $C_i$ 円で打っていて価値は $V_i$ である.
高橋くんの最初の所持金は $0$ であり,以下の通りに行動する.

  1. 高橋くんは財宝を売却するか,商品を購入するかを決める.売却なら手順2へ,購入なら手順3へ.
  2. 高橋くんは持ってる財宝の中で最も番号が小さい財宝を売る.青木くんは売り出している商品の1つを選び販売を停止する.手順1へ戻る.
  3. 高橋くんは販売中の商品を好きなだけ買う.手順1に戻らずこれで終了する.

高橋くんは買う商品の価値の総和をできるだけ高くするように行動する.
逆に青木くんはできるだけ低くなるように行動する.
買う商品の価値の総和を求める問題.

解法

まず,前計算として,最後に購入するときの高橋くんの最適な行動を動的計画法で求める.
つまり,
 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)$ でも通る.

cLayversion 20180208-1)のコード

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)

ログイン: