SRM 519 div1 med:RequiredSubstrings

言われてみると桁DPの一般化っぽい感じ。

問題

TopCoder Statistics - Problem Statement

解法

主となるアイデアは桁DPとほとんど変わりません。つまり,

ある文字列の状態(stateとする)にaからzのいずれかの文字を追加した時の次の状態(nextstateとする)とした時に,

dp[i+1][nextstate] += dp[i][state]

とするようなイメージです。

この解法で解くときに注意しなければならないのは,

・状態をどのように定義するか
・状態の遷移はどうなるか
・結局答えを求めるにはどうすればええんや

コードでそれぞれstate, nextState, stateAddでやっています。words[]のstringそれぞれの部分文字列を状態として,末尾に文字を追加した時の次の状態をnextStateにして,ある状態での文字列の末尾にwords[i]の文字があればi文字目があるというフラグを立てておきます。

これを使ってdpすればOKです。

const ll MOD = 1e9+9;

ll dp[55][500][64];

class RequiredSubstrings {
public:
    int solve(vector <string> words, int C, int L) {
        map<string, int> state;
        int S = 0;
        int n = words.size();
        // stateの列挙
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= words[i].size(); j++) {
                string tmp = words[i].substr(0, j);
                if (state.find(tmp) == state.end()) {
                    state.insert(make_pair(tmp, S++));
                }
            }
        }
        cout << S << endl;
        // stateの遷移
        vector<vi> nextState(S, vi(26));
        for (auto p : state) {
            for (int i = 0; i < 26; i++) {
                string nstr = p.first + (char)('a'+i);
                while (state.find(nstr) == state.end()) nstr = nstr.substr(1);
                nextState[p.second][i] = state[nstr];
            }
        }
        // stateの判定
        vector<int> stateAdd(S);
        for (auto p : state) {
            string str = p.first;
            int s = p.second;
            int add = 0;
            for (int j = 0; j < n; j++) {
                if (str.size() < words[j].size()) continue;
                if (str.substr(str.size()-words[j].size()) == words[j]) add |= (1<<j);
            }
            stateAdd[s] = add;
        }
        // dp
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1; // l, state, flag
        for (int i = 0; i < L; i++) for (int s = 0; s < S; s++) for (int flag = 0; flag < (1<<n); flag++) {
            if (dp[i][s][flag] == 0) continue;
            for (int j = 0; j < 26; j++) {
                int ns = nextState[s][j];
                int nflag = flag;
                nflag |= stateAdd[ns];
                (dp[i+1][ns][nflag] += dp[i][s][flag]) %= MOD;
            }
        }
        ll ans = 0;
        for (int i = 0; i < (1<<n); i++) {
            if (__builtin_popcount(i) != C) continue;
            for (int j = 0; j < S; j++) {
                (ans += dp[L][j][i]) %= MOD;
            }
        }
        return (int)ans;
    }