SRM 503 div1 easy:ToastXToast

SRM練習会に参加。結果はeasyだけ解いてはい。

問題

TopCoder Statistics - Problem Statement

解法

結構本番不安だったんですがメモ化再帰で解きました。

undertoastedとovertoastedがソートされているとします。

「1種類のパンを考慮するときにundertoastedとovertoastedはどのような関係になっているのか」ということを考えてみます。パンがちょうど美味しく焼ける時間はすべてのundertoastedの時間より長く,すべてのovertoastedの時間よりも短くなければならないという制約があります。よって,以下のようにすれば良いです(めんどくさいのでundertoastedをut, overtoastedをotと書くことにします)：

dp[u][o] := (u番目までのutとo番目までのotはすでに確定しているとする。この時,utのu番目からの時間とotのo番目からの時間を使ってパンの種類を考える時,パンの種類の最小数はいくつか)
というdpを考える。これを解くには,

パンを焼く時間を示す整数の組(i, j)(i >= u, j >= o)を考える(ut[u]からut[i]までの時間で焼くとundertoastedになってot[o]からot[j]の時間で焼くとovertoastedになるということ)。この時ut[i] < ot[o]が成り立っていなければならない。これでパン1種類が確定したので次にdp[i+1][j+1]を考える,...というような感じでメモ化再帰を作れば良い。最終的に選ぶのはそれらの整数の組(i, j)のうち最小のもの。

以下ソースコード

int dp[55][55];
int n, m;
const int INF = 1e9;
vector<int> ut, ot;

int dfs(int u, int o) {
    if (u == n && o == m) return 0;
    if (u == n) return INF;
    if (o == m) return INF;
    int& ret = dp[u][o];
    if (ret >= 0) return ret;
    ret = INF;
    for (int i = u; i < n; i++) {
        if (ut[i] > ot[o]) break;
        for (int j = o; j < m; j++) {
            ret = min(ret, 1+dfs(i+1, j+1));
        }
    }
    return ret;
}

class ToastXToast {
public:
    int bake(vector <int> undertoasted, vector <int> overtoasted) {
        ut = undertoasted;
        ot = overtoasted;
        sort(ot.begin(), ot.end());
        sort(ut.begin(), ut.end());
        n = undertoasted.size();
        m = overtoasted.size();
        memset(dp, -1, sizeof(dp));
        int ans = dfs(0, 0);
        if (ans == INF) ans = -1;
        return ans;
    }
};