Codeforces Round #222 (Div. 1) C. Captains Mode

このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp)

問題

codeforces.com

解法

pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。

これを考えると, pick されるものとして考えるべきものは, 上位 m 個のみであるとわかります。

そこで, まず dp[turn][state] = (turn 目で, まだ pick も ban もされていない上位 m 人の状態が state である時の最適値)
という dp が考えられます。遷移では, turn 目で誰を pick/ban するかが m 通りあるので, 計算量は O(m^2 2^m) です。

C++ だとこれでも通りそうですが, ban する人はバラバラであると考えても良いこと, そう考えると turn は state のうち bit がたっているものの数で与えられることを考慮すると, dp[state] という状態だけで遷移ができるので, 計算量は O(m 2^m) です。

const int INF = 1e9;
int n, m;
int s[111], team[22];
int dp[1<<20];
char action[22];

int dfs(int state) {
    int& ret = dp[state];
    if (ret > -INF) return ret;
    int turn = __builtin_popcount(state);
    if (turn == m) return ret = 0;
    if (team[turn] == 1) {
        ret = -INF/2;
        if (action[turn] == 'p') {
            for (int i = 0; i < m; i++) {
                if ((state>>i&1) == 0) {
                    ret = max(ret, s[i]+dfs(state|(1<<i)));
                    break;
                }
            }
        } else {
            for (int i = 0; i < m; i++) {
                if ((state>>i&1) == 0) {
                    ret = max(ret, dfs(state|(1<<i)));
                }
            }
        }
    } else {
        ret = INF/2;
        if (action[turn] == 'p') {
            for (int i = 0; i < m; i++) {
                if ((state>>i&1) == 0) {
                    ret = min(ret, -s[i]+dfs(state|(1<<i)));
                    break;
                }
            }
        } else {
            for (int i = 0; i < m; i++) {
                if ((state>>i&1) == 0) {
                    ret = min(ret, dfs(state|(1<<i)));
                }
            }
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s, s+n);
    reverse(s, s+n);
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> action[i] >> team[i];
    }
    for (int i = 0; i < (1<<m); i++) dp[i] = -INF;
    cout << dfs(0) << endl;
    return 0;
}