mayoko’s diary

プロコンとかいろいろ。

SRM 469 div1 med:TheMoviesLevelTwoDivOne

典型っぽいけど解けてよかった。

問題:TopCoder Statistics - Problem Statement

解法:まず制約からなんとなくbitDPな感じがします。ということでbitDPに落とし込みたいんですが,よく考えるとあるところまで映画が眠ることなく見終わったとすると,その時のJohnの覚醒レベルがわかります。
よって,n種類の映画を見た/見ないによる2^nの状態を保持しておいて,その時における覚醒レベルを計算し,その後に何種類の映画を見れるかを更に別の状態への遷移として計算していけばいけそうです。
もうちょいキレイな実装ありそうですが,具体的な実装はこんな感じでやりました。
基本的にはdfs(s)を使ってメモ化再帰です。中では
・覚醒レベルの計算
・次の映画が見れるかのチェック,見れるならベストな視聴方法をさらに次のdfsに投げる
ということをやっています。
で,このやり方だと困るのが,映画を見れなかった場合に次のdfsに進んでくれないので,dpの値が初期値のままだったりします。しかし,dpの値が初期値の場合はどうせその状態になる時には眠っているということなので,そこからは貪欲に辞書順最小的な感じにすればOKということになります。それはdfs(0)を呼び出した後にやっているやつです。
以下ソースコード

pair<int, int> dp[1<<22];
vector<int> scary, length;
int n;

pair<int, int> dfs(int s) {
    if (s == (1<<n)-1) {
        return make_pair(0, -1);
    }
    if (dp[s] != make_pair(-100, -100)) return dp[s];
    int level = 74;
    for (int i = 0; i < n; i++) {
        if ((s>>i)&1) {
            level += 47-length[i];
        }
    }
    // bestのやつを探す
    pair<int, int> best = make_pair(-10, -10);
    for (int i = 0; i < n; i++) {
        if (((s>>i)&1)==0) {
            if (best == make_pair(-10, -10)) best = make_pair(-1, i);
            // 途中で寝ないかチェック
            bool ng = false;
            if (2*scary[i] > 2*level+1) ng = true;
            else if (2*(level+47-length[i]) < -1) ng = true;
            if (!ng) {
                auto p = dfs(s|(1<<i));
                if (best.first < p.first+1) {
                    best = make_pair(p.first+1, i);
                }
            }
        }
    }
    return dp[s] = best;
}

class TheMoviesLevelTwoDivOne {
public:
    vector <int> find(vector <int> l, vector <int> sc) {
        length = l;
        scary = sc;
        n = length.size();
        for (int s = 0; s < (1<<n); s++) dp[s] = make_pair(-100, -100);
        dfs(0);
        for (int i = 0; i < (1<<n); i++) {
            if (dp[i].first == -100) {
                for (int j = 0; j < n; j++) {
                    if (((i>>j)&1) == 0) {
                        dp[i].second = j;
                        break;
                    }
                }
            }
        }
        vector<int> ans;
        int s = 0;
        for (int i = 0; i < n; i++) {
            int next = dp[s].second;
            ans.push_back(next);
            s |= 1<<next;
        }
        return ans;
    }
};