駆引取引 [「みんなのプロコン 2018」C]

https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_c

解法

https://yahoo-procon2018-qual.contest.atcoder.jp/submissions/2083670

方針としてはminimaxのようにやっていく。
「f(n, msk) := n品売って購入可能な商品の集合がmskである場合の最大価値」
を再帰を使って、計算していく。
関数fの内部では高橋君が「売却」か「購入」を選択する。
「売却」の場合では、どの商品を買えなくするかを全て試し、その場合の最大価値の最小値を採用する。
これは青木君が得点を最小化するように行動するためである。
「購入」の場合では、購入可能な商品mskをX[0]+...+X[n-1]のお金で買った時の最大価値となる。
あとは、この2選択のうち大きい方を高橋君の選択として採用して答えればいい。
　
問題は「購入」の場合の計算コストだが、事前計算ができる。
「dp[n][msk] := n個売却して購入可能商品がmskの場合の最大価値」
これを計算するために、まずはdpを以下のように考えて構築しよう。
「dp[n][msk] := n個売却して商品集合msk全てを購入した場合の最大価値（購入できないなら0）」
これを計算するのはそんなに難しくない。
このdpを最初のdpに変換するには、「dp[n][msk] := max{msk' ⊆ msk}dp[n][msk']」という計算をすればいい。
これはO(3^N)でやっても間に合うが、メビウス変換的な事をすればO(N*2^N)で済む。
　
関数fは状態O(N*2^N)で計算量O(N)なので、全体はO(N^2*2^N)

int N; ll X[20], C[20], V[20];
ll dp[20][1 << 18];
vector<pair<ll, ll>> v;
//---------------------------------------------------------------------------------------------------
ll memo[20][1 << 18];
ll f(int n, int msk) {
    if (0 <= memo[n][msk]) return memo[n][msk];
    if (n == N) return 0;
 
    // 売却
    ll sold = infl;
    rep(i, 0, N) if (msk & (1 << i)) chmin(sold, f(n + 1, msk - (1 << i)));
 
    // 購入
    ll buy = dp[n][msk];
 
    return memo[n][msk] = max(sold, buy);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) cin >> C[i];
    rep(i, 0, N) cin >> V[i];
 
    rep(n, 0, N + 1) {
        ll yen = 0;
        rep(i, 0, n) yen += X[i];
        
        rep(msk, 0, 1 << N) {
            ll co = 0, va = 0;
            rep(i, 0, N) if (msk & (1 << i)) co += C[i], va += V[i];
            if (co <= yen) dp[n][msk] = va;
            else dp[n][msk] = 0;
        }
 
        rep(msk, 0, 1 << N) rep(i, 0, N) if (msk & (1 << i)) chmax(dp[n][msk], dp[n][msk ^ (1 << i)]);
    }
 
    rep(i, 0, N + 1) rep(msk, 0, 1 << N) memo[i][msk] = -1;
    cout << f(0, (1 << N) - 1) << endl;
}