New Year Contest 2015 : C - 文字列の書き換え

本番えらい面倒なコードで通したのに、ある事実に気づくとあっさり。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_3

問題

文字列Sに対し、以下の処理を任意回数行う。

• S中の文字を１つ選び、その直後にそれとは異なる文字を１文字挿入する。

文字列Tが与えられるとき、上記処理の繰り返しによりSをTに出来るか答えよ。

解法

本番では、T中の各1文字に上記処理を繰り返したとき、最大でT中の何文字分に変換できるかDPで求めたうえで、Tに変換可能なTの部分文字列としてSがありうるかを求めた。

しかし、以下の事実に気づくともっと簡単な処理でかける。
「ある１文字の文字列Xに対し、上記処理を繰り返し行うと、１文字目がXであり、２文字目X以外である２文字以上任意長の文字列が生成できる」

以下の簡単なDPでO(|S||T|)で解ける。
S,Tの部分文字列に対し、S[0..x]からT[0..y]が生成可能とする。
さらにS[x+1]==T[y+1]なら：

• S[0..x+1]からT[0..y+1]が生成できる。
• さらにT[y+1]!=T[y+2]なら、S[0..x+1]からT[0..z] (y+2≦z≦|T|-1)が全て生成できる。

string S,T;
int LS,LT;
int ok[5002][5002];

void solve() {
	int i,j,k,l,r,x,y,y2; string s;
	
	cin>>S>>T;
	LS=S.size();
	LT=T.size();
	ok[0][0]=1;
	FOR(x,LS) {
		FOR(y,LT) if(ok[x][y]&&S[x]==T[y]) {
			if(ok[x+1][y+1]) continue;
			ok[x+1][y+1]=1;
			if(y<LT-1 && T[y]!=T[y+1]) {
				for(y2=y+2;y2<=LT;y2++) ok[x+1][y2]=1;
			}
		}
	}
	
	if(ok[LS][LT]) _P("Yes\n");
	else _P("No\n");
}

まとめ

本番かなり迷って時間もかかったんだけどなぁ。