AOJ 2249: 桜詩 願はくは花の下にて春死なむ / Sakura Poetry

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257

他の人の解法を見るに想定はAho-Corasickらしいが、そんなものは不要。

solution

愚直に動的計画法。(詩の長さ, 最後の単語, 季語が含まれているか, 季語判定に必要な詩の末尾) $\mapsto$ そのような詩の数、のようにする。 遷移は接続辞書に従って単語を追加していい感じにするだけ。 季語判定に必要な詩の末尾の種類数は$X \approx 3000$ぐらいで抑えられて、$O(MNXK)$とかそんな感じになる。

これを素直にやると間に合わないので高速化。 (最後の単語, 季語が含まれているか, 季語判定に必要な詩の末尾) $\mapsto i$として写し、そのような写された$i$上で状態遷移グラフを再構築するとよい。 つまりは最大までメモ化されて、$O(MN + XK)$みたいな感じになるはず。 非想定解法っぽいが十分速いのでこれでよい。

implementation

#include <iostream>
#include <map>
#include <tuple>
#include <unordered_map>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

bool is_suffix(string const & a, string const & b) {
    if (a.length() > b.length()) return false;
    return b.compare(b.length() - a.length(), b.length(), a) == 0;
}

int count_seasonwords(string const & s, vector<string> const & seasonwords) {
    int cnt = 0;
    for (string const & seasonword : seasonwords) {
        for (int j = 0; ; ) {
            j = s.find(seasonword, j);
            if (j == string::npos) break;
            ++ j;
            ++ cnt;
            if (cnt >= 2) return cnt;
        }
    }
    return cnt;
}

string shrink_to_seasonwords(string s, vector<string> const & seasonwords) {
    int len = 0;
    for (string const & seasonword : seasonwords) {
        string t = seasonword;
        if (t.length() > s.length()) t = t.substr(0, s.length());
        for (; not t.empty(); t.pop_back()) {
            if (is_suffix(t, s)) {
                setmax<int>(len, t.length());
                break;
            }
        }
    }
    return s.substr(s.length() - len);
}

constexpr int mod = 1e9+7;
int main() {
    while (true) {
        // input
        int n, m, k; cin >> n >> m >> k;
        if (n == 0) break;
        multimap<string, string> conn;
        repeat (i, n) {
            string from, to; cin >> from >> to;
            conn.emplace(from, to);
        }
        vector<string> seasonword(k);
        repeat (i, k) {
            cin >> seasonword[i];
        }
        // solve
        vector<string> word;
        map<string, int> index;
        for (auto const & it : conn) {
            for (string s : { it.first, it.second }) {
                if (not index.count(s)) {
                    index.emplace(s, index.size());
                    word.push_back(s);
                }
            }
        }
        vector<vector<int> > g(word.size());
        for (auto const & it : conn) {
            g[index[it.first]].push_back(index[it.second]);
        }
        map<tuple<int, bool, string>, int> compression;
        vector<tuple<int, bool, string> > uncompress;
        vector<bool> used;
        vector<vector<pair<int, int> > > h;
        auto compress = [&](int i, bool is_season, string const & s) {
            auto key = make_tuple(i, is_season, s);
            auto it = compression.find(key);
            if (it != compression.end()) return it->second;
            compression.emplace(key, compression.size());
            uncompress.push_back(key);
            used.push_back(false);
            h.emplace_back();
            return int(compression.size()) - 1;
        };
        vector<map<int, int> > dp(m + 1);
        repeat (i, word.size()) if (word[i].length() <= m) {
            int season = count_seasonwords(word[i], seasonword);
            if (season >= 2) continue;
            dp[word[i].length()][compress(i, bool(season), word[i])] += 1;
        }
        repeat (l, m) {
            for (auto state : dp[l]) {
                int p, cnt; tie(p, cnt) = state;
                if (not used[p]) {
                    used[p] = true;
                    int i; bool is_season; string s; tie(i, is_season, s) = uncompress[p];
                    int count_seasonwords_s = count_seasonwords(s, seasonword);
                    for (int j : g[i]) {
                        if (m < l + word[j].length()) continue; // this is ok
                        string t = s + word[j];
                        int next_season = is_season + count_seasonwords(t, seasonword) - count_seasonwords_s;
                        if (next_season >= 2) continue;
                        int q = compress(j, bool(next_season), shrink_to_seasonwords(t, seasonword));
                        h[p].emplace_back(q, word[j].length());
                    }
                }
                for (auto edge : h[p]) {
                    int q, dl; tie(q, dl) = edge;
                    if (m < l + dl) continue;
                    int & it = dp[l + dl][q];
                    it += cnt;
                    if (it >= mod) it -= mod;
                }
            }
            dp[l] = map<int, int>(); // release
        }
        // output
        int result = 0;
        for (auto state : dp[m]) {
            int p, cnt; tie(p, cnt) = state;
            bool is_season; tie(ignore, is_season, ignore) = uncompress[p];
            if (not is_season) continue;
            result = (result + cnt) % mod;
        }
        cout << result << endl;
    }
    return 0;
}