UnKoder #02 Animal Party

最初もっと高速なアルゴリズムにするつもりだったけど,なんかWAが出るので方針を変えた。

問題:Programming Problems and Competitions :: HackerRank

解法:メモ化再帰を使う。問題の性質上,パーティーに招待される動物は
イヌ->ネコ->イヌ->ネコ->...
ネコ->イヌ->ネコ->イヌ->...
のどちらかになるので,最初にイヌになるかネコになるかを決めて,その後は「このイヌ/ネコの区間でどれくらい時間を使うか」を決めて,次の時間はネコ/イヌでどれくらい時間を使うか,...というように決めていく。
以下ソースコード

const int MAXN = 64;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[111][2];
int N, M;

int dfs(int t, int mode) {
    int& ret = dp[t][mode];
    if (ret >= 0) return ret;
    ret = 0;
    if (mode == 0) {
        for (int T = t+1; T <= 100; T++) {
            int num = 0;
            for (int i = 0; i < N; i++) {
                if (t <= a[i] && b[i] <= T) num++;
            }
            ret = max(ret, num+dfs(T, 1));
        }
    } else {
        for (int T = t+1; T <= 100; T++) {
            int num = 0;
            for (int i = 0; i < M; i++) {
                if (t <= c[i] && d[i] <= T) num++;
            }
            ret = max(ret, num+dfs(T, 0));
        }
    }
    return ret;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> c[i] >> d[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << max(dfs(0, 0), dfs(0, 1)) << endl;
}

すぎむさん良い問題出すよなぁ。すごい。