CODE THANKS FESTIVAL 2015 : E - ノイズ除去

なんかいい順位取れた。タイム的には1時間切りたかったけど、ノーミスだったのがありがたい。
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_e

問題

文字列S,Tが与えられる。
Sから一部の文字を取り除く(同じ種類の文字はすべて取り除く)ことができるとき、取り除いた後のSの連続部分文字列としてTを含むようにできるか。

解法

取り除く場合は同じ文字を全て取り除かなければならないので、単にSの部分文字列としてTを含むか判定してはダメである。
そこで、Tの1文字目をSのどこに対応付けるかを総当たりしよう。

あとはSとTを1文字ずつ比較していって、一致しないなら「この文字はSから取り除く文字」、一致するなら「この文字はSに残す文字」と判断していく。
各文字が「残す文字」「取り除く文字」両方に入ってしまうという矛盾が生じず、かつ最終的に|T|文字分Sから適切に残せるなら、題意を満たす。

int Q;
string S,T;

void solve() {
	int i,j,k,l,r,x,y,s;
	
	cin>>Q;
	while(Q--) {
		cin>>S>>T;
		int LS=S.size(),LT=T.size();
		FORR(r,S) r-='a';
		FORR(r,T) r-='a';
		
		int ok=0;
		FOR(s,LS) if(S[s]==T[0]) {
			y=0;
			int pat[26]={};
			int ok2=1;
			for(x=s;x<LS && y<LT;x++) {
				if(pat[S[x]]==0) pat[S[x]]=2-(S[x]==T[y]);
				if(pat[S[x]]==1) {
					if(S[x]!=T[y]) {
						ok2=0;
						break;
					}
					y++;
				}
				if(pat[S[x]]==2) {
					if(S[x]==T[y]) {
						ok2=0;
						break;
					}
				}
			}
			if(ok2 && y>=LT) ok=1;
		}
		
		if(ok) _P("YES\n");
		else _P("NO\n");
	}
}

まとめ

連続部分文字列でないといけないという部分を読み落としたため、大幅タイムロスした。