本番えらい面倒なコードで通したのに、ある事実に気づくとあっさり。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_3
問題
文字列Sに対し、以下の処理を任意回数行う。
- S中の文字を1つ選び、その直後にそれとは異なる文字を1文字挿入する。
文字列Tが与えられるとき、上記処理の繰り返しによりSをTに出来るか答えよ。
解法
本番では、T中の各1文字に上記処理を繰り返したとき、最大でT中の何文字分に変換できるかDPで求めたうえで、Tに変換可能なTの部分文字列としてSがありうるかを求めた。
しかし、以下の事実に気づくともっと簡単な処理でかける。
「ある1文字の文字列Xに対し、上記処理を繰り返し行うと、1文字目がXであり、2文字目X以外である2文字以上任意長の文字列が生成できる」
以下の簡単な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"); }
まとめ
本番かなり迷って時間もかかったんだけどなぁ。