TopCoder SRM 836 : Div1 Medium DoubleWordLadder

こちらはまんまとコーナーケースにやられた。
https://community.topcoder.com/stat?c=problem_statement&pm=17794

問題

アルファベット小文字で構成された、同じ長さの文字列A,Bが与えられる。
Aのうち1文字を任意のアルファベット小文字に置き換える、ということを繰り返し、AをBにしたい。
ただし以下の条件を満たす変換法を取らなければならない。

• A[i]→B[i]と直接置き換えてはならない。1度他の文字を経由する必要がある。
• 同じ位置を2回連続置き換えてはならない。

置き換え回数最小の手順のうち、途中の文字列を順に並べたとき、辞書順最小となるものを答えよ。

解法

置き換え回数を最小化したいので、元々A[i]=B[i]である位置は、基本的には(後述)置き換えることはない。
他の位置は、2手で置き換えることになる。経由する文字は、A[i]でもB[i]でもない最小のアルファベットとなる。

あとは貪欲に以下のように行おう。

• 置き換え位置の候補のうち、置き換え後が辞書順最小となるものから順に置き換えを試みる。
  • ただし以下の時は、置き換えられない。
    • 直前と同じ位置である。
    • 残された置き換え方法が、1か所の位置でかつあと2回置き換えが必要である。

基本これでいいのだが、1つコーナーケースがある。
AとBが1文字だけ異なるケースである。この場合、他の文字を1個選び、あえて一度別の文字に置き換える必要がある。
この時は、置き換え先の文字列が辞書順最小になりそうなものを選ぼう。

int T[33];
int S[33][2];
char C[33];
class DoubleWordLadder {
	public:
	vector <string> transform(string A, string B) {
		int N=A.size();
		string C;
		int i,j;
		ZERO(S);
		ZERO(T);
		int num=0;
		FOR(i,N) {
			if(A[i]==B[i]) {
				T[i]=2;
			}
			else {
				num++;
				C[i]='a';
				while(C[i]==A[i]||C[i]==B[i]) C[i]++;
				S[i][0]=(A[i]<C[i])?1:-1;
				S[i][1]=(C[i]<B[i])?1:-1;
			}
		}
		if(num==1) {
			FOR(i,N) if(num<2&&A[i]==B[i]&&A[i]!='a') {
				num++;
				T[i]=0;
				C[i]='a';
				S[i][0]=(A[i]<C[i])?1:-1;
				S[i][1]=(C[i]<B[i])?1:-1;
			}
			for(i=N-1;i>=0;i--) if(num<2&&A[i]==B[i]&&A[i]=='a') {
				num++;
				T[i]=0;
				C[i]='b';
				S[i][0]=(A[i]<C[i])?1:-1;
				S[i][1]=(C[i]<B[i])?1:-1;
			}
		}
		
		vector<string> R={A};
		int pre=-1;
		while(1) {
			vector<pair<int,int>> V;
			FOR(i,N) if(i!=pre&&T[i]<2) {
				if(S[i][T[i]]==-1) V.push_back({0,i});
				else V.push_back({100-i,i});
			}
			if(V.empty()) break;
			sort(ALL(V));
			FORR(a,V) {
				i=a.second;
				T[i]++;
				int num=0,sum=0;
				FOR(j,N) if(T[j]!=2) num++, sum+=2-T[j];
				if(num==1&&sum==2) {
					T[i]--;
					continue;
				}
				R.push_back(R.back());
				if(T[i]==1) {
					R.back()[i]=C[i];
				}
				else {
					R.back()[i]=B[i];
				}
				pre=i;
				cout<<R.back()<<endl;
				break;
			}
			
		}
		assert(R.back()==B);
		return R;
		
	}
}

まとめ

1文字だけ異なるケースにまんまとやられた。