みんなのプロコン 2018 C - 駆引取引

• 問題

問題概要

Nターンのゲームをする. 値段x[i],価値v[i],費用c[i] が与えられる.
先手は前からx[i]を売るか,それまで得た値段を払ってmax_(i in {1..N})(v[i])を得てゲームを終了する.
後手は先手の価値を最小化するように価値を取り除く
先手の最大スコアを求めよ.

解法

dp[i][S] := (Sの品物が残っている状態でiターン目から得られる最大の価値)
solve(i,S) := (iターン目からSが残っている状態で得られる最大の価値) とする.
Sはビット列で管理する.

dp[i][S]が分かっていれば
先手はゲームを終了/売るのうち最大の方を選べば良く,
売るの方を選択すると後手は利益を最小化するように品物を除いてくるので solve(i,S) := max(dp[i][S], min_(s in 残っている品物のうちどれか)(solve(S\s)) で解ける.
これはメモ化すれば N*2^N. 答えは solve(0,all) になる.

dp[i][S]を求める. まず全てのSについて価値valと費用costを出し,
費用がiターンまでに得た値段以下のものを dp[i][S] = val とする.
次に全てのSについて,iがSに含まれていなければ dp[i∪S] = max(dp[i∪S],dp[S]) と遷移すれば解ける.

O(N²*2^N)で,軽めのO(10⁸)ぐらいなので間に合う.

メモ

CODE THANKS FESTIVALのFとほとんど同じだし,良く出る遷移っぽい.
また配列サイズ間違うクソみたなバグを埋め込んでしまった. vectorで管理した方がいいのかなあ.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 33;

ll dp[20][(1<<18)];
ll x[20],c[20],v[20],s[20],cost[(1<<18)],val[(1<<18)];
int N;

inline bool contain(int bit,int i){
  return (bit>>i)&1;
}

int main(){
  cin >> N;
  Pl vc[20];
  rep(i,N) cin >> x[i];
  rep(i,N) cin >> c[i];
  rep(i,N) cin >> v[i];
  s[0] = 0LL;
  rep(i,N) s[i+1] = s[i] + x[i];
  rep(i,N) rep(j,1<<N) dp[i][j] = 0LL;
  fill(cost,cost+(1<<18),0LL);
  fill(val,val+(1<<18),0LL);
  
  rep(j,1<<N){
    rep(k,N) if(contain(j,k)) cost[j] += c[k], val[j] += v[k];
  }
  rep(i,N){
    rep(j,1<<N) if(cost[j]<=s[i]) dp[i][j] = max(dp[i][j],val[j]);
  }

  rep(i,N){
    rep(j,1<<N){
      if(__builtin_popcount(j)>N-i) continue;
      rep(k,N) if(contain(j,k)) dp[i][j] = max(dp[i][j],dp[i][j^(1<<k)]);
    }
  }

  map<P,ll> memo;
  function<ll(int,int)> solve = [&](int a,int b){
    if(memo.count(P(a,b))) return memo[P(a,b)];
    if(a==N) return 0LL;
    ll res = dp[a][b];
    ll temp = LINF;
    rep(i,N) if(contain(b,i)) temp = min(temp,solve(a+1,b^(1<<i)));
    return memo[P(a,b)] = max(res,temp);
  };
  cout << solve(0,(1<<N)-1) << endl;
  return 0;
}