Facebook Hacker Cup 2016 Round 1 Coding Contest Creation

問題

https://www.facebook.com/hackercup/problem/798506286925018/

解法

dp[now][num] = (now 個目の問題がコンテストの num 問目で使われる時の追加すべき問題の最小値) という dp をやります。

D[now] > 100-(3-num) だと, コンテスト最後の問題の難易度が 100 を超えてしまうので NG です。
そうでない場合は, now 問目と now+1 問目と同じコンテストの問題にするかしないかで場合分けします。

D[now+1] = 1 だったりすると, now+1 問目を 2 問目にすることは出来ないこととかに注意しましょう。

const int MAXN = 100010;
int N;
int dp[MAXN][4], D[MAXN];

int dfs(int now, int num) {
    int& ret = dp[now][num];
    if (ret >= 0) return ret;
    int should = 100-(3-num);
    if (D[now] > should) return ret = 4*MAXN;
    if (now == N-1) {
        return ret = 3-num;
    }
    // now と now+1 をつなげない
    // now+1 の考慮
    ret = dfs(now+1, 0);
    if (D[now+1] > 1) ret = min(ret, 1+dfs(now+1, 1));
    if (D[now+1] > 2) ret = min(ret, 2+dfs(now+1, 2));
    if (D[now+1] > 3) ret = min(ret, 3+dfs(now+1, 3));
    // now を終わらせる(now が終わることは保証されている)
    ret += 3-num;
    // now と now+1 をつなげる
    int diff = D[now+1]-D[now];
    if (1 <= diff && diff <= 10 && num < 3) {
        ret = min(ret, dfs(now+1, num+1));
    }
    if (2 <= diff && diff <= 20 && num < 2) {
        ret = min(ret, 1+dfs(now+1, num+2));
    }
    if (3 <= diff && diff <= 30 && num < 1) {
        ret = min(ret, 2+dfs(now+1, num+3));
    }
    return ret;
}

void solve(int T) {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    memset(dp, -1, sizeof(dp));
    int ans = dfs(0, 0);
    if (D[0] > 1) ans = min(ans, 1+dfs(0, 1));
    if (D[0] > 2) ans = min(ans, 2+dfs(0, 2));
    if (D[0] > 3) ans = min(ans, 3+dfs(0, 3));
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}