AOJ 2249: 桜詩 願はくは花の下にて春死なむ / Sakura Poetry
他の人の解法を見るに想定は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;
}