GCJ Round3 Problem B. Forest University

問題

Dashboard - Round 3 2016 - Google Code Jam

長さ N の文字列が与えられる。また, 「i 番目の文字は j 番目の文字が現れた後しか現れてはいけない」という条件が与えられる。

このような条件を満たす文字列はたくさん考えられるが, この中で「できた文字列が query[i] を部分文字列として持つ」確率はいくらか求めよ。

解法

許容誤差が大きいので, 乱択でいけそうな気がします。何も考えずに s の random_shuffle だけを考える方針は, 現れる文字列が 0 -> 1 -> 2 -> ... -> n しかないような場合に死ぬので, これは良くないです。そこで, 「乱択はするけど, 考える文字列は確実にあり得るものだけにしたい」という要請があります。これがこの問題の主題です。

ここで問題で与えられる条件を考えてみると, 各 index は一つだけ「それより前に来なければならない index」を指定されています。これは, 木構造で parent を指定する構造と同じなので, 木DP のようなことが使えそうです。

ある頂点 v の後に ch0, ch1, ... が来ることがわかっているとすると, (ch0 以降を使う文字列), (ch1 以降を使う文字列) というのが生成できます。そして, これらの文字列を(chi 以降を使う文字列) としての順番は崩さずにシャッフルします。すると, いい感じにあり得る文字列で乱択をすることが可能です。

下のコードは LOOP が大きすぎたのと自分の PC がややポンコツなことが合わさって結構時間かかりました。

const int LOOP = 50000;

string dfs(int v, const vector<vi>& G, const string& s) {
    string ret;
    for (int ch : G[v]) {
        string t = dfs(ch, G, s);
        vector<int> r(ret.size()+t.size());
        fill(r.begin(), r.begin()+t.size(), 1);
        random_shuffle(r.begin(), r.end());
        string next;
        int tcnt = 0, retcnt = 0;
        for (int i = 0; i < ret.size()+t.size(); i++) {
            if (r[i]) next += t[tcnt++];
            else next += ret[retcnt++];
        }
        ret = next;
    }
    ret = s[v]+ret;
    return ret;
}

void solve() {
    int N;
    cin >> N;
    vector<vi> G(N+1);
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> p;
        G[p].push_back(i);
    }
    string s;
    cin >> s;
    s = "$"+s;
    int M;
    cin >> M;
    vector<string> query(M);
    for (int i = 0; i < M; i++)
        cin >> query[i];
    vector<double> ans(M);
    for (int i = 0; i < LOOP; i++) {
        string t = dfs(0, G, s);
        for (int j = 0; j < M; j++) {
            if (t.find(query[j]) != string::npos) ans[j] += 1;
        }
    }
    for (int i = 0; i < M; i++) {
        printf("%.3lf", ans[i]/LOOP);
        if (i < M-1) printf(" ");
    }
    printf("\n");
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": " ;
        solve();
    }
    return 0;
}

木DP でモンテカルロする空間を絞れるの結構面白いと思いました。