SRM 542 div1 med: StrangeDictionary2

問題

TopCoder Statistics - Problem Statement

同じ長さ L の文字列が n 個与えられる。これを辞書順にソートするのだが, ソートの仕方が少し特殊で, 長さ L の順列 p が与えられて, p[0] 番目の文字, p[1] 番目の文字, ..., p[L-1] 番目の文字, という順番でソートことにする。
順列 p の与え方がランダム(L! 通りある)のとき, 1 番はじめにくる文字が i 番目の文字列である確率はいくらであるか。0<= i < n すべてについて求めよ。

解法

dp[i][s] = (集合 s の中で i が最も先頭に来る確率) とします。答えは, dp[0][2^n - 1], dp[1][2^n - 1], ... を並べたことになります。

集合 s のそれぞれの l 番目の文字を見に行った時, 異なる文字が存在するなら, l 番目の文字で区別される文字があるということなので, 集合 s のサイズが減ります。こんな感じで遷移を作っていくと良いです。

というのは, dfs(i, 2^n - 1) からメモ化再帰を始めた場合, 集合 s に含まれる要素というのは, 「それまでの文字は全部一致している」という条件を満たしているので, l 番目の文字を見てすべて一致しているようなら遷移には関係ないもの, または既に辞書順で調べたものとして無視し, そうでないなら順列を順番に見ていった時に初めて出てきた文字として処理すれば良いからです。

これで概ね良いのですが, この問題では制約をかなり攻めているので, 一つの状態を計算するのに O(Ln) かけると TLE します。
なので, nextSet[s][l] = (集合 s が生き残っている時, l 番目の文字を次に比較したらその後に生き残っている集合はなにか) というのを前計算しておきましょう。これで O(2^n nL) になって間に合います。C++ で 500ms 弱かかっているので python だと死にそうですが。

double dp[16][1<<16];
int nextSet[1<<16][55];
vector<string> words;
int n, L;

// 集合 s の中で i が最も先頭に来る確率
double dfs(int i, int s) {
    double& ret = dp[i][s];
    if (ret >= 0) return ret;
    if (__builtin_popcount(s) == 1) return ret = 1;
    ret = 0;
    vi v;
    int cnt = 0;
    for (int j = 0; j < L; j++) {
        int ns = nextSet[s][j];
        if (ns != s) {
            cnt++;
            if (ns&(1<<i)) v.push_back(j);
        }
    }
    for (int el : v) {
        int ns = nextSet[s][el];
        ret += dfs(i, ns)/cnt;
    }
    return ret;
}

class StrangeDictionary2 {
public:
    vector <double> getProbabilities(vector <string> words) {
        ::words = words;
        n = words.size();
        L = words[0].size();
        for (int i = 0; i < n; i++) for (int s = 0; s < 1<<n; s++) dp[i][s] = -1;
        for (int s = 0; s < 1<<16; s++) {
            for (int l = 0; l < L; l++) {
                char mini = 'z';
                for (int i = 0; i < n; i++) if ((s>>i)&1) {
                    mini = min(mini, words[i][l]);
                }
                int ns = 0;
                for (int i = 0; i < n; i++) if ((s>>i)&1) {
                    if (words[i][l] == mini) ns |= 1<<i;
                }
                nextSet[s][l] = ns;
            }
        }
        vector<double> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = dfs(i, (1<<n)-1);
        }
        return ans;
    }
};