ICPC2013国内予選F - hirokazu1020の日記

F問題が良問だったので解説記事を書くことにしました。
The 2013 ACM-ICPC Asia Aizu Regional Contest :: Domestic contest problem set
解法は

という神々の言葉を聞いてなんとかわかりましたがヒントなしじゃとても解ける気がしないです。
この問題を解くには最初にCYK法で全ての部分区間についてある文字に変えられるかを調べる必要があります。
標準的なCYK法では書き換えルールは xy→z のように2文字から1文字に変えるルールしかないので、CYK内部で部分区間[i,j]をxy→zで書き換えられるかは Any(dp[i][k][x] And dp[k+1][j][y]) (k=i,i+1..,j-1)
で判定できますが、この問題では書き換え前の列の長さが2より大きいものがルールに含まれるので上記の方法ではできません。
ですがCYK法は区間DPなのである区間について考えるときその部分区間がある文字に書き換えられるかは全て求まっています。
なのでCYK内部で、ある区間をあるルールで書き換えられるかという問題は「文字列についてそれぞれの区間がある文字に変換できるという条件下で、与えられた文字列をある文字列に変換できるか」という問題として表せます。
これなら普通にコンテストの問題として出そうだしそれほど難しくもないDPで解けます。
つまりCYK内部である区間をあるルールで書き換え可能かの判定のためにさらにDPするわけです。

次にこの問題の厄介そうなルールに「回転」がありますがこれはあまり考えなくていいです。
というのも循環させて見れば回転しても並びの順番は変わらないからです。
ただし典型区間DPでは[a,b] (a<=b) というような区間しか考えないのですが(a>b)のような場合でも回転することによって(ab)となる区間も調べる必要があります。
区間DPではある区間はそれより短い区間に依存するので区間の長さが短い順に確定させていけば何も考えなくてもトポロジカル順序を満たすので、区間DPを[a,b] (a>b)にも対応できるように拡張するのは簡単にできます。

あとはnm通りの回転の仕方について2つの列を最長一致させるDPすればいいだけですね。

実装面では数列に現れる数値の範囲は1〜30なので変換できる値はビットフラグで持っています。
これによって最後の2つの列を一致させる部分にビット毎の論理積を使えるので高速化できます。
計算量は O((n^4+m^4)rk + n^3m^3)

コメントなしの読みにくいコードですが見たい人はどうぞ

#include<iostream>
#include<cstring>
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

struct Rule{
	vector<int> x;
	int y;
};

void CYK(int trans[25][25],vector<Rule> &rule,vector<int> s){
	memset(trans,0,sizeof(int)*25*25);
	rep(i,s.size()){
		trans[i][i] |= 1<<s[i];
	}
	bool dp[26][11];
	rep(j,s.size()){
		rep(i,s.size()){
			rep(k,rule.size()){
				if(j+1<rule[k].x.size())continue;
				memset(dp,false,sizeof(dp));
				dp[0][0]=true;
				rep(g,j+1){
					rep(h,rule[k].x.size()){
						if(!dp[g][h])continue;
						rep(f,j+1-g){
							if(trans[(i+g)%s.size()][(i+g+f)%s.size()]>>rule[k].x[h]&1)
								dp[g+f+1][h+1]=true;
						}
					}
				}
				if(dp[j+1][rule[k].x.size()]) trans[i][(i+j)%s.size()] |= 1<<rule[k].y;
			}
		}
	}
}
int main(){
	int n,m,r;
	vector<int> a,b;
	vector<Rule> rule;
	int transa[25][25],transb[25][25];
	int dp[26][26];
	while(cin>>n>>m>>r,n|m|r){
		a.resize(n);
		b.resize(m);
		rep(i,n)cin>>a[i];
		rep(i,m)cin>>b[i];
		rule.resize(r);
		rep(i,r){
			int k,v;
			cin>>k;
			rule[i].x.resize(k);
			rep(j,k){
				cin>>v;
				rule[i].x[j]=v;
			}
			cin>>rule[i].y;
		}
		CYK(transa,rule,a);
		CYK(transb,rule,b);
		int ans=-1;
		int sa=a.size(),sb=b.size();
		rep(i,n){
			rep(j,m){
				memset(dp,-1,sizeof(dp));
				dp[0][0]=0;
				rep(k,n){
					rep(f,m){
						if(dp[k][f]==-1)continue;
						rep(g,n-k){
							rep(h,m-f){
								if(transa[(i+k)%sa][(i+k+g)%sa] & transb[(j+f)%sb][(j+f+h)%sb]) dp[k+g+1][f+h+1]=max(dp[k+g+1][f+h+1],dp[k][f]+1);
							}
						}
					}
				}
				ans=max(ans,dp[n][m]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}