Problem 2022 : Princess, a Cryptanalyst

問題概要

日本語なので本文参照。
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2022）

解法

最短共通部分列問題（呼称合ってる？）
与えられた全ての文字列を（連続する）部分列として含むような文字列を求める。

これは以前にPKUで同様の問題を解いた通り、d[i][j]をi番目の文字列からj番目の文字列を付け加えるのにかかるコスト（重複する文字を除いた分の文字数）として、
巡回セールスマンぽく（というかハミルトン路）ビットDPすればよい。
前に書いた解法は実は効率が悪くて（スタートをn通り試してO(n^2 2^n)にしてしまっていた）、
初期化をdp[i][1<<i]=len(i)とすれば、一度のDPで全ての出発点からの最短路が求まる。

この問題では辞書順最小の文字列を求める必要があるので、
dp[i][j]に、距離ではなくて、現在iの頂点にいて、ビットjで表される配列の頂点を訪れたときの最適な文字列そのものを入れておく。

文字列を入れなくてもいい気がするんだけど、それだと辞書順最小をどうだすのかわからなかったorz
laycurseさんの解法とかタイムからみるに明らかに文字列そのものはもってない気が。

ソースコード

int n,m;
string in[10],d[10][10],ans[10][1<<10];

void MIN(string &a,string b){
	if(a.empty()||a.size()>b.size()||a.size()==b.size()&&a>b)a=b;
}
string solve(){
	rep(i,n)rep(j,1<<n)ans[i][j].clear();
	rep(i,n)ans[i][1<<i]=in[i];
	rep(j,1<<n)rep(i,n)if(j&1<<i)rep(k,n)if(!(j&1<<k))
	MIN(ans[k][j^1<<k],ans[i][j]+d[i][k]);
	string ret;
	rep(i,n)MIN(ret,ans[i][(1<<n)-1]);
	return ret;
}
int main()
{
	while(scanf("%d",&m),m){
		string s[10];
		rep(i,m)cin>>s[i];
		sort(s,s+m); m=unique(s,s+m)-s;
		bool con[10]={0};
		rep(i,m)rep(j,m)if(i!=j)if(s[i].find(s[j])!=string::npos)con[j]=1;
		n=0; rep(i,m)if(!con[i])in[n++]=s[i];
		
		rep(i,n)rep(j,n){
			int a=in[i].size(),b=in[j].size();
			for(int l=min(a,b);l>=0;l--){
				rep(k,l)if(in[i][a-l+k]!=in[j][k])goto NG;
				d[i][j]=in[j].substr(l); break;
				NG:;
			}
		}
		cout<<solve()<<endl;
	}
	return 0;
}