TopCoder SRM 617 Div1 Hard FarStrings

800ptとはいえこれは自力では解けなかったかな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12526

問題

文字列SとTの距離は、Sに以下の処理を行ってTにするのに必要な最小処理回数である。

• 任意の１文字を任意の位置に挿入する
• 任意の１文字を削除する
• 任意の１文字を別の文字に変える

文字列Tが与えられる。
文字列の長さをNとしたとき、Tとの距離が1,2,3...NとなるN文字の文字列のうち、それぞれ辞書順最小のものを答えよ。

解法

自力で解けなかったので他の回答を見て練習。

求める文字列、すなわちTとの距離がiの文字列をU[i]とする。
U[i]の１文字目からa, b, c...と埋めていき、U[i]がそのようなprefixを持つとき、U[i]とTの距離の最小値と最大値を求める。
iが最大値と最小値の間に来るような文字があれば、それを採用していく。

問題はU[i]をprefixとする文字列とTの距離。
これはLongest Common Stringの要領でDPしていき、最小値を求めていく。
その際、Tの文字が完了する前にU[i]のprefixとマッチし終わった場合、残りの文字をTの残りと合わせるか合わせないかで距離の最小・最大値の範囲を求められる。

N<=25なため、必ずTのどれともマッチしないアルファベットが存在するので、最大値を取ることは常に可能。

class FarStrings {
	public:
	
	pair<int,int> dist(string A,string B,int bl) {
		int al=A.size();
		int dp[51][51],dp2[51][51],x,y;
		FOR(x,51) FOR(y,51) dp[x][y]=dp2[x][y]=10000;
		dp[0][0]=dp2[0][0]=0;
		
		FOR(x,al+1) FOR(y,al+1) {
			if(x<al) dp[x+1][y]=min(dp[x+1][y],dp[x][y]+1), dp2[x+1][y]=min(dp2[x+1][y],dp2[x][y]+1);
			if(y<al) dp[x][y+1]=min(dp[x][y+1],dp[x][y]+1), dp2[x][y+1]=min(dp2[x][y+1],dp2[x][y]+1);
			if(x<al) {
				if(y<bl) {
					dp[x+1][y+1]=min(dp[x+1][y+1],dp[x][y]+(A[x]!=B[y]));
					dp2[x+1][y+1]=min(dp2[x+1][y+1],dp2[x][y]+(A[x]!=B[y]));
				}
				else if(y<al) {
					dp[x+1][y+1]=min(dp[x+1][y+1],dp[x][y]);
					dp2[x+1][y+1]=min(dp2[x+1][y+1],dp2[x][y]+1);
				}
			}
		}
		
		return pair<int,int>(make_pair(dp[al][al],dp2[al][al]));
	}
	
	vector <string> find(string t) {
		int ss=t.size(),i,j;
		vector<string> S;
		
		FOR(i,ss) {
			string h=string(ss,'*');
			FOR(j,ss) {
				for(h[j]='a';h[j]<='z';h[j]++) {
					pair<int,int> p=dist(t,h,j+1);
					if(p.first<=i+1 && i+1<=p.second) break;
				}
			}
			S.push_back(h);
		}
		return S;
	}
};

まとめ

prefixマッチ完了後の最大・最小値の処理は自分では思い浮かばなかったわ…。