東京工業大学プログラミングコンテスト2015 : G - titech分離

どんどん行きます。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_g

問題

文字列Sを(非連続でもよい)いくつかの部分文字列に分解する。
各部分文字列が"titech"となるようにできるか判定せよ。

解法

titechと1文字一致するごとに以下のように遷移するオートマトンを考える。
(開始)→1→2→3→4→5→6(ゴール)
入力がL文字とすると、上記オートマトンがL/6個あり、１文字ごとでどれか１個のオートマトンを１個状態遷移すると考える。

あとは各状態のオートマトンが何個あるか、を状態としてDFSしていくとよい。
全オートマトンが終了状態に遷移してたら条件を満たす。

なお、想定解法では同じオートマトンにしてももう少し軽い(tで分岐の生じない)方法をとってO(L)で終わるようにしているようだ。

char did[17][17][17][17][17][17];
int L;
string S;

void dfs(int cur,vector<int>& v) {
	if(cur==L) {
		if(v[0]+v[1]+v[2]+v[3]+v[4]+v[5]) return;
		_P("Yes\n");
		exit(0); 
	}
	
	if(did[v[0]][v[1]][v[2]][v[3]][v[4]][v[5]]) return;
	did[v[0]][v[1]][v[2]][v[3]][v[4]][v[5]] = 1;
	int i;
	if(S[cur]=='t') {
		i=0; if(v[i]&&v[i+1]<L/6) v[i]--, v[i+1]++, dfs(cur+1,v), v[i]++, v[i+1]--;
		i=2; if(v[i]&&v[i+1]<L/6) v[i]--, v[i+1]++, dfs(cur+1,v), v[i]++, v[i+1]--;
	}
	else if(S[cur]=='i') {
		i=1; if(v[i]&&v[i+1]<L/6) v[i]--, v[i+1]++, dfs(cur+1,v), v[i]++, v[i+1]--;
	}
	else if(S[cur]=='e') {
		i=3; if(v[i]&&v[i+1]<L/6) v[i]--, v[i+1]++, dfs(cur+1,v), v[i]++, v[i+1]--;
	}
	else if(S[cur]=='c') {
		i=4; if(v[i]&&v[i+1]<L/6) v[i]--, v[i+1]++, dfs(cur+1,v), v[i]++, v[i+1]--;
	}
	else if(S[cur]=='h') {
		i=5; if(v[i]) v[i]--, dfs(cur+1,v), v[i]++;
	}
	else {
		_P("No\n");
		exit(0);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	if(L%6) return _P("No\n");
	
	vector<int> v(6,0);
	v[0]=L/6;
	dfs(0,v);
	
	_P("No\n");
	
}

まとめ

正規表現とかでさらっと書けたりしないのかな？