Google Code Jam 2014 Round 1C : B. Reordering Train Cars

これはちょっと苦戦したけど何とか解けた。
https://code.google.com/codejam/contest/3004486/dashboard#s=p1

問題

N個の単語が与えられる。
これらのN個の単語を連結した際、同じ文字同士はすべて連結してる状態にしたい。
そのような単語の並び方の組みあわせを答えよ。

なお、連結後の文字列が一緒でも、元単語の並べ方が異なれば別の並びとみなす。

解法

まず、後の処理を簡単にするため、個々の単語中で同じ文字が連続している場合、それを消して１個だけ残すようにしておく。

最初に指定の並びができない場合を先に判定使用。

• ある単語において真ん中、すなわち先頭及び末尾以外の文字が他の単語にも含まれる場合、それらを隣接させることはできないので、題意は満たせない。
• 個々の単語において、同じ文字が複数回含まれる場合、それらを隣接させることはできないので、題意は満たせない。（最初から連結している場合、最初の処理でそれらは１個になっているはずなので、複数同じ文字があるというのは間に他の文字が挟まっていることを示す。）
• a..bとa..cのように、異なる末尾で同じ先頭の単語群があってはならない。この場合両単語のa同士をつなげることができない。
• b..dとc..dのように、同じ末尾で末尾が先頭と異なる単語群があってはならない。この場合両単語のa同士をつなげることができない。

次に、各文字の先頭と末尾のみに注目する。

• a..bとb..cというようにある単語の末尾と別単語の先頭が同じ文字なら、それらは連結させなければならない。
• 1文字の場合、たとえば、aという単語は、上記a..bの前にたくさんつけることができる。

上記条件より、先頭の文字が他の単語の末尾に来ない単語は先頭に来れる可能性がある。
この手順を々、先頭に来れる単語の数xを求めると、答えはその並び順x!となる。
例えば、a..b、b..c、c..dの一連の単語群と、e..f、f..g、g..hとi..j、j..k、k..lの単語群がある場合、a..b～c..d、e..f～g..h、i..j～k..lの３つの単語群の並び順は3!=6である。

ただし、間に1文字の単語がy個ある場合、それらの並び順は任意なのでy!倍する。
例えばbが4個あればa..bとb..cの間にbを4!通り挟むことができる。

int N;
string S[101],TS;
char C[101][2];

int tar[26];
ll mo=1000000007;
int ishead[26];
ll kai[505];
int same[26];

ll dfs(int cur) {
	if(cur==-1) return 1;
	return dfs(tar[cur])*kai[same[cur]]%mo;
}

int isloop(int cur,int dst) {
	if(tar[cur]==-1) return 0;
	if(tar[cur]==dst) return 1;
	return isloop(tar[cur],dst);
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	kai[0]=1;
	FOR(i,500) kai[i+1]=kai[i]*(i+1)%mo;
	MINUS(tar);
	ZERO(same);
	
	cin>>N;
	
	
	FOR(i,N) cin>>S[i];
	FOR(i,N) {
		string s2;
		s2+=S[i][0];
		for(x=1;x<S[i].size();x++) if(S[i][x-1]!=S[i][x]) s2+=S[i][x];
		for(x=1;x<s2.size()-1;x++) {
			FOR(y,N) if(i!=y && count(S[y].begin(),S[y].end(),s2[x])>0) return _P("Case #%d: 0\n",_loop);
		}
		FOR(x,s2.size()) FOR(y,s2.size()) if(x!=y && s2[x]==s2[y]) return _P("Case #%d: 0\n",_loop);
		
		if(s2[0]==s2[s2.size()-1]) {
			same[s2[0]-'a']++;
		}
		else {
			if(tar[s2[0]-'a']>=0) return _P("Case #%d: 0\n",_loop);
			tar[s2[0]-'a']=s2[s2.size()-1]-'a';
		}
	}
	
	ZERO(ishead);
	FOR(i,26) ishead[i]=1;
	FOR(i,26) if(tar[i]>=0) ishead[tar[i]]=0;
	FOR(i,26) if(ishead[tar[i]]==0 && isloop(i,i)) return _P("Case #%d: 0\n",_loop);
	FOR(i,26) if(tar[i]==-1 && same[i]==0) ishead[i]=-1;
	
	int num=0;
	ll ret=1;
	FOR(i,26) if(ishead[i]==1) num++, ret=ret*dfs(i)%mo;
	ret *= kai[num];
	
	_P("Case #%d: %lld\n",_loop,ret%mo);
}

まとめ

結構面倒くさいが何とか解けてよかった。