AOJ 2257 Sakura Poetry

SRM Div1 medを解いていたら,解法が浮かんだ.
ローカルで通すのは簡単だけど,AOJで通すにはメモリ管理が必要．

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

解法
DP + Aho-corasick
季語の集合をAho-corasickを使って,オートマトンを作成
dpテーブルは,dp[文字列の長さ][単語][季語を使ったかどうか][オートマトンの状態]とする.
オートマトンの状態数の上限は季語の集合の全文字数より,30*20=600通り
単語数の上限は接続辞書の単語数より，250*2=500通り
単語の遷移の上限は500*500ではなく，接続辞書の情報数の上限250通り
よって，500*250*600*2 =1.5*10^9になるが，ローカルで解ける．また，dpテーブルはスパースなのでAOJでも間に合う．
時間計算量はO(MNK)
AOJのメモリ制限では,dp[501][500][601][2]という配列を用意すると,MLE
しかし，このdpテーブルはスパースなので，mapなどを使うことでMLEを回避できる.

ソースコードは以下の通り

#include <bits/stdc++.h>
#define range(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) range(i,0,n)
using namespace std;

typedef long long ll;

int n,m,k;
string words[510];
string from[255],to[255];
string season[35];

int fg[610][27];
int ac[610];

int build(){
	memset(fg,0,sizeof(fg));
	memset(ac,0,sizeof(ac));
	int root=1,size=2;
	fg[root][0]=root;
	rep(i,k){
		int cur=root;
		rep(j,season[i].size()){
			int tar=season[i][j]-'a'+1;
			if(fg[cur][tar]==0) fg[cur][tar]=size++;
			cur=fg[cur][tar];
		}
		ac[cur]|=(1<<i);
	}
	queue<int> q;
	range(i,1,27){
		if(fg[root][i]){
			fg[fg[root][i]][0]=root;
			int tar=fg[root][i];
			q.push(tar);
		}else
			fg[root][i]=root;
	}
	while(!q.empty()){
		int now=q.front();q.pop();
		range(i,1,27){
			if(fg[now][i]){
				int tar=fg[now][0];
				while(!fg[tar][i]) tar=fg[tar][0];
				fg[fg[now][i]][0]=fg[tar][i];
				ac[fg[now][i]]|=ac[fg[tar][i]];
				q.push(fg[now][i]);
			}
		}
	}
	return size;
}

const ll mod=1000000007;
map<int,int> dp[510][510][2]; // len words ac state

int main(void){
	ios::sync_with_stdio(false);
	while(cin >> n >> m >> k){
		if(n==0) break;

		rep(i,n) cin >> from[i] >> to[i];
		rep(i,n) words[2*i]=from[i];
		rep(i,n) words[2*i+1]=to[i];
		sort(words,words+2*n);
		int w=unique(words,words+2*n)-words;

		rep(i,k) cin >> season[i];
		int root=1,s=build();

		vector<int> graph[510];
		rep(i,n){
			int fi=lower_bound(words,words+w,from[i])-words;
			int ti=lower_bound(words,words+w,to[i])-words;
			graph[fi].emplace_back(ti);
		}
		rep(i,w) graph[w].emplace_back(i);

		dp[0][w][0][root]=1LL;
		rep(i,m){
			rep(j,w+1)range(k,root,s)rep(l,2){
				if(i>0&&j==w) continue;
				if(dp[i][j][l].find(k)==dp[i][j][l].end()) continue;
				for(auto &nj:graph[j]){
					int ni=i+words[nj].size();
					if(ni>m) continue;
					int nk=k,nl=l;
					rep(a,words[nj].size()){
						int tar=words[nj][a]-'a'+1;
						while(!fg[nk][tar]) nk=fg[nk][0];
						nk=fg[nk][tar];
						nl+=__builtin_popcount(ac[nk]);
						if(nl>=2) break;
					}
					if(nl>=2) continue;
					dp[ni][nj][nl][nk]+=dp[i][j][l][k];
					dp[ni][nj][nl][nk]%=mod;
				}
			}
			rep(j,w+1)rep(l,2) dp[i][j][l].clear();
		}
		int ans=0LL;
		rep(j,w+1)for(auto &i:dp[m][j][1]){
			ans+=i.second;
			ans%=mod;
		}
		cout << ans << endl;
		rep(j,w+1)rep(l,2) dp[m][j][l].clear();
	}
	return 0;
}