JAG Contest 2016 Domestic D - インビジブル

誤読死しました。

問題

jag2016-domestic.contest.atcoder.jp

わからなくてここを読みに来てる人はとりあえず問題文を読みなおすことをオススメします。

解法

スタックに積まれるカード群は必ず [l, r) と言った区間的になることに注目します。これに気づくと, 途中で相手から妨害カードが来た時も [l, r) が有効 -> [r, r) が有効, と変更すれば良いこともわかります。

ここまで気づけば,
dp[l1][r1][l2][r2] = (プレイヤー 1 は実質的に [l1, r1) までスタックに積んでいて, プレイヤー 2 は[l2, r2) までスタックに積んである時に, 得点の差を最大化するスコア)
とすれば良さ気であることに気づきます。

あと, 「今どっちのターンか」「スタックが空になってからパスが何回続いているか」を状態に持てば普通に dp 出来ます。

int n, m;
const int MAX = 55;
const int INF = 1e9;

int a[MAX], b[MAX];
int asum[MAX], bsum[MAX];
int dp[MAX][MAX][MAX][MAX][2][3];

// [l1, r1) 区間, [l2, r2) 区間がスタックに入ってる
int dfs(int l1, int r1, int l2, int r2, int turn, int flag) {
    int& ret = dp[l1][r1][l2][r2][turn][flag];
    if (ret > -INF) return ret;
    // パスする
    ret = asum[r1]-asum[l1];
    ret -= bsum[r2]-bsum[l2];
    if (!(flag==1 && (r1-l1==0 && r2-l2==0))) {
        ret += dfs(r1, r1, r2, r2, turn^1, flag+(r1-l1==0&&r2-l2==0));
    }
    if (turn == 0) {
        // 出す
        if (r1 < n) {
            if (a[r1] == -1) {
                ret = max(ret, dfs(l1, r1+1, r2, r2, turn^1, 0));
            } else {
                ret = max(ret, dfs(l1, r1+1, l2, r2, turn^1, 0));
            }
        }
    } else {
        // 出す
        if (r2 < m) {
            if (b[r2] == -1) {
                ret = min(ret, dfs(r1, r1, l2, r2+1, turn^1, 0));
            } else {
                ret = min(ret, dfs(l1, r1, l2, r2+1, turn^1, 0));
            }
        }
    }
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    for (int i = 0; i < n; i++) asum[i+1] = asum[i] + (a[i]==-1 ? 0 : a[i]);
    for (int i = 0; i < m; i++) bsum[i+1] = bsum[i] + (b[i]==-1 ? 0 : b[i]);
    for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) {
        for (int k = 0; k < MAX; k++) for (int l = 0; l < MAX; l++) {
            for (int x = 0; x < 2; x++) for (int y = 0; y < 3; y++) {
                dp[i][j][k][l][x][y] = -INF;
            }
        }
    }
    cout << dfs(0, 0, 0, 0, 0, 0) << endl;
    return 0;
}