kmjp's blog

競技プログラミング参加記です

Code Formula 2014 予選B : C - 仲良し文字列

WAしてしまったのが残念。
http://code-formula-2014-qualb.contest.atcoder.jp/tasks/code_formula_2014_qualB_c

問題

A,B2つの文字列が与えられる。

A中2つの異なる位置の文字を入れ替える、という処理を3回ぴったり行い、AをBに出来るか答えよ。

解法

まずA,Bのうち異なる文字についてカウントする。
文字入れ替えは3回までなので、最大でも6文字しか入れ替え対象にならないので、異なる文字は6文字以下でなければならない。

あとはA,Bの異なる文字は6文字なので、総当たりで2文字選んで3回入れ替えを行えばよい。
なお、A,Bのうち異なる文字数が0文字や1文字だったりすると、入れ替えが実行できなくなる。
その場合、A,Bに何文字か同じ文字を加えて入れ替え対象にすればよい。

string A,B;
string C,D,E;
int aa[6];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>A>>B;
	if(A.size()>6) {
		FOR(i,A.size()) {
			if(A[i]!=B[i]) C+=A[i],D+=B[i];
			else E+='A';
		}
		if(C.size()>6) return _P("NO\n");
		C+=E;
		D+=E;
		if(C.size()>6) C=C.substr(0,6),D=D.substr(0,6);
	}
	else {
		C=A,D=B;
	}
	
	FOR(aa[0],C.size()) FOR(aa[1],C.size()) FOR(aa[2],C.size()) FOR(aa[3],C.size()) FOR(aa[4],C.size()) FOR(aa[5],C.size()) {
		if(aa[0]==aa[1]) continue;
		if(aa[2]==aa[3]) continue;
		if(aa[4]==aa[5]) continue;
		string C2=C;
		swap(C2[aa[0]],C2[aa[1]]);
		swap(C2[aa[2]],C2[aa[3]]);
		swap(C2[aa[4]],C2[aa[5]]);
		if(C2==D) return _P("YES\n");
	}
	_P("NO\n");
	
}

まとめ

異なる文字数が少ないときにWA、をいうのを案の定やってしまった。