SRM 674 div2 hard:VampireTreeDiv2

うーん, SRM のコード提出できないんですが…(なぜかこのコードは web arena で提出したら AC した)
あとで div1 med も解説載せますがこっちは AC したことを確かめてないです(というか誰かに確かめて欲しい)

問題

解法

まず「親と子」という関係がなく「マスターとサーヴァント」という関係のみの場合を考えると, グラフは木になります。この場合はよくある木 DP をやれば良いです。

dp[v][need] = (頂点 v をサンプルに入れる必要性が need で表される(need = 0 なら必要なし, need = 1 なら必要あり))時に, v 以下の部分木でサンプルに入れる必要のある頂点の最小値, 及びそのパターン数
とします。
need = 1 の場合は v の各子 ch について dp[ch][0] を求め, パターンを計算する以外手段が無いです。
一方, need = 0 の場合は v をサンプルに入れるかサンプルに入れないかで場合分け出来ます。少ない方を選びましょう(同じ場合はパターンは２つの合計になる)。

一般に「親と子」の関係がある場合も考えてみます。この関係があるようなものはたかだか 15 種類しか無いので, 次のような場合分けが出来ます。すなわち, 子を絶対にサンプルに入れるか, 絶対にサンプルに入れないか, です。

子をサンプルに入れる場合は, 親はサンプルする必要は無いです。一方で, 子をサンプルに入れない場合は, 親は両方ともサンプルに入れなければなりません。
そこで, must0[v] = (v を絶対にサンプルに入れないかどうか), must1[v] = (v を絶対にサンプルに入れるかどうか) というに種類のフラグを用意して, 上と同じように木 dp をやります。木 dp をやるので, B[i] と i+1 の頂点をつないではいけません。

ところで, ここが結構混乱したんですが, 「絶対サンプルに入れない」と言っておきながら「絶対サンプルに入れる」となることがあります(ある親の子でありながら, ある子の親であるような頂点がありえるので)。下のコードではその場合を無視しています(というか最小値がアホみたいに大きくなるので実質的に無視できる)。

const int MAXN = 1024;
const ll MOD = 1e9+7;
pair<int, ll> dp[MAXN][2];
pair<int, ll> memo[1<<15];
vector<int> G[MAXN];
// must0: true なら絶対に選ばない
// must1: true なら絶対に選ぶ
bool must0[MAXN], must1[MAXN];

pair<int, ll> dfs(int v, int need) {
    if (dp[v][need].first >= 0) return dp[v][need];
    int mini = MAXN;
    ll pat = 0;
    if (!must0[v]) {
        int mini0 = 1;
        ll pat0 = 1;
        for (int u : G[v]) {
            auto p = dfs(u, 0);
            mini0 += p.first;
            (pat0 *= p.second) %= MOD;
        }
        mini = mini0;
        pat = pat0;
    }
    if (need == 0 && !must1[v]) {
        int mini0 = 0;
        ll pat0 = 1;
        for (int u : G[v]) {
            auto p = dfs(u, 1);
            mini0 += p.first;
            (pat0 *= p.second) %= MOD;
        }
        if (mini > mini0) {
            mini = mini0;
            pat = pat0;
        } else if (mini == mini0) {
            (pat += pat0) %= MOD;
        }
    }
    return dp[v][need] = make_pair(mini, pat);
}

class VampireTreeDiv2 {
public:
    int countMinSamples(vector <int> A, vector <int> B) {
        int n = A.size()+1;
        for (int i = 0; i < n; i++) G[i].clear();
        vector<int> child;
        for (int i = 0; i < n-1; i++) {
            G[A[i]].push_back(i+1);
            if (B[i] != -1) child.push_back(i);
        }
        int size = child.size();
        int mini = MAXN;
        for (int s = 0; s < (1<<size); s++) {
            memset(must0, false, sizeof(must0));
            memset(must1, false, sizeof(must1));
            for (int i = 0; i < size; i++) {
                if ((s>>i)&1) must1[child[i]+1] = true;
                else {
                    must0[child[i]+1] = true;
                    must1[A[child[i]]] = must1[B[child[i]]] = true;
                }
            }
            for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) {
                dp[i][j].first = -1;
            }
            memo[s] = dfs(0, 0);
            mini = min(mini, memo[s].first);
        }
        ll ans = 0;
        for (int s = 0; s < (1<<size); s++) {
            if (mini == memo[s].first) (ans += memo[s].second) %= MOD;
        }
        return (int)ans;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 674 div2 hard:VampireTreeDiv2

問題

解法