TCO15 Round 2C easy:YetAnotherCardGame

TCO15 Round 2Cに参加しました。ゼロ完でちーん。

問題

TopCoder Statistics - Problem Statement

解法

一番ポイントなのは,「パスするときに飛ばすカードは,後から決めれば良い」ということです。

これに気づくと,dp[今一番上にあるカードの数][ターン数]でdpをすれば良いということがわかります。

今のターンに一番上にあるカードの番号がわかっている時,プレーヤーが取れる行動は,「何か食う」か「カードを置く」かのいずれかです。何かを食う場合は次の人が何かを置くはずなのでそれらの場合をすべて考えてそのmaxを取れば答えが得られます。

int dp[101][101];
vi card[2];
int n;

int dfs(int cur, int turn) {
    if (turn == 2 * n) return 0;
    if (turn > 2*n) return -100;
    int& ret = dp[cur][turn];
    if (ret >= 0) return ret;
    int who = (turn&1);
    ret = 0;
    for (int i = 0; i < n; i++) {
        if (card[who][i] > cur) {
            ret = max(ret, 1+dfs(card[who][i], turn+1));
        }
    }
    for (int i = 0; i < n; i++) {
        if (card[1-who][i] > cur) {
            ret = max(ret, 1+dfs(card[1-who][i], turn+2));
        }
    }
    return ret;
}

class YetAnotherCardGame {
public:
    int maxCards(vector <int> petr, vector <int> snuke) {
        n = petr.size();
        card[0] = petr;
        card[1] = snuke;
        for (int i = 0; i < 2; i++) sort(card[i].begin(), card[i].end());
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0);
    }
};