TopCoder SRM 432 Div1 Medium GroupedWord

問題

文字列がgrouped wordであるとは、
同じ種類のアルファベットの二文字の間に他のアルファベットがはさまれていないことを言う。

文字列を連続する部分文字列に区切った集合が与えられる。
元の文字列が一意に復元できるならその文字列を、
複数通りに復元できるならMANYを、
元の文字列が存在しないとき、IMPOSSIBLEを返せ。

制約条件

集合の要素の個数≦50
それぞれの文字列の長さ≦50

方針

まず、ひとつだけのアルファベットからなる文字列を、すべて他の文字列につなげておく。

文字列Aの末尾と、文字列Bの先頭の文字が一致するとき、Aの直後にBをつなげてよい。
また、他につなげかたは存在しない。

全ての文字列をこの操作を繰り返して一つの文字列に出来たら、それが答え。
複数の文字列が残ったら、それらがvalidだったならば（つなげたときにgroupedにならないようなペアが存在しないなら）、それらはどうつなげてもよいので、MANY
そうでないならIMPOSSIBLEになる。

ソースコード

ちょっと試験的に演算子の間に空白を入れるようにしてみる。

class GroupedWord {
	public:
	string restore(vector <string> parts) 
	{
		while(parts.size() > 1) {
			bool update = 0;
			rep(i, parts.size()) {
				bool single = 1;
				rep(j, parts[i].size())single &=parts[i][j] == parts[i][0];
				if(!single) continue;
				rep(j, parts.size())if(i != j && parts[j][0] == parts[i][0]){
					parts[j] = parts[i] + parts[j];
					update = 1;
					parts.erase(parts.begin() + i);
					goto NEXT;
				}
				rep(j, parts.size())
				if(i != j && parts[j][parts[j].size() - 1] == parts[i][0]){
					parts[j] += parts[i];
					update = 1;
					parts.erase(parts.begin() + i);
					goto NEXT;
				}
			}
			rep(i, parts.size())rep(j, parts.size())if(i != j) {
				if(parts[i][parts[i].size()-1] == parts[j][0]){
					parts[i] += parts[j];
					parts.erase(parts.begin() + j);
					update = 1;
					goto NEXT;
				}
			}
			if(!update) break;
			NEXT:;
		}
		
		rep(i,parts.size())cerr<<parts[i]<<endl;
		
		rep(i, parts.size())rep(j, parts.size())if(i != j) {
			rep(k, parts[i].size())rep(l, parts[j].size()) {
				if(parts[i][k] != parts[j][l]) continue;
				
				bool suf = 1, pre = 1;
				for(int m = k + 1; m < parts[i].size(); m++)
					if(parts[i][m] != parts[i][k])suf = 0;
				rep(m, l) 
					if(parts[j][m] != parts[j][l])pre = 0;
				if(!suf || !pre) return "IMPOSSIBLE";
			}
		}
		
		rep(i, parts.size())rep(k, parts[i].size())rep(j, k)
		if(parts[i][j] == parts[i][k])
			for(int l = j; l < k; l++)if(parts[i][j] != parts[i][l])
				return "IMPOSSIBLE";
		return parts.size() > 1 ? "MANY" : parts[0];
};