TopCoder SRM 677 Div2 Medium FourStrings

３連続調子よかったのに最後の最後で0完…辛うじて1Chal。
https://community.topcoder.com/stat?c=problem_statement&pm=14099

問題

4つの文字列a,b,c,dが与えられる。
これら４つを含む文字列のうち最短の長さを求めよ。

解法

next_permutationで順番を変えながら、aにb,c,dのsuffixを総当たりで連結してa,b,c,dを含むかチェックしたら通った。

class FourStrings {
	public:
	
	int shortestLength(string a, string b, string c, string d) {
		int i,ret=6060,j;
		vector<string> V={a,b,c,d};
		FOR(i,24) {
			int L[4]={};
			for(L[1]=0;L[1]<=V[1].size();L[1]++)
			for(L[2]=0;L[2]<=V[2].size();L[2]++)
			for(L[3]=0;L[3]<=V[3].size();L[3]++) {
				string s=V[0].substr(L[0])+V[1].substr(L[1])+V[2].substr(L[2])+V[3].substr(L[3]);
				if(s.size()>ret) continue;
				int ok=1;
				FOR(j,4) if(s.find(V[j])==string::npos) ok=0;
				if(ok) ret=s.size();
			}
			next_permutation(V.begin(),V.end());
		}
		return ret;
		
	}
}

まとめ

550ptというだけあっていつもよりは少し難しめ。