kmjp's blog

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

Codeforces #324 Div2 C. Marina and Vasya

体調はいまいちだがなぜか出来は良かった。
http://codeforces.com/contest/584/problem/C

問題

N文字の文字列2つS1,S2と整数Tが与えられる。
同じ長さの文字列a,bに対し、f(a,b) := 両文字列のうち同じ位置の文字が異なっているものの数 とする。
f(S1,S3)=f(S2,S3)=TとなるようなS3を作成せよ。

解法

アルファベットは26種類あるので、S1・S2・S3がある位置で一致するようにするのは大変だが、S1・S2・S3が互いに異なるようにするようは容易である。
よって、S1とS3、S2とS3でT文字異なっていると考えず、(N-T)文字一致させると考えよう。

S1とS2が元々P文字一致してたとする。
(N-T)≦Pなら、S3においてP文字中(N-T)文字一致させ、残りは(元々S1とS2が異なっていた部分も含め)S3をS1・S2のどちらとも異なるようにすればよい。
P<(N-T)の場合、元々一致していたP文字をS3と一致させるだけでは足りないので、S1とS2が異なる部分(N-P)文字のうち一部を用いて(N-T)文字一致するようにする。
これら(N-P)文字において、S3はS1とS2のどちらかとしか一致させられない点に注意。
(N-P)/2<(N-T)-Pの場合、条件を満たせない。

int N,T;
string S[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	T=N-T;
	cin>>S[0]>>S[1];
	int dif=0;
	FOR(i,N) if(S[0][i]!=S[1][i]) dif++;
	int same=N-dif;
	
	S[2]=S[1];
	FOR(i,N) if(S[0][i] == S[1][i]) {
		if(T) T--;
		else S[2][i] = (S[2][i]=='a')?'b':'a';
	}
	
	T*=2;
	FOR(i,N) if(S[0][i] != S[1][i]) {
		if(T) {
			S[2][i]=S[T%2][i];
			T--;
		}
		else {
			char c='a';
			while(c==S[0][i] ||c==S[1][i]) c++;
			S[2][i]=c;
		}
	}
	
	if(T) return _P("-1\n");
	cout<<S[2]<<endl;
}

まとめ

みんなアプローチがバラバラだし、コードも複雑になりがちでHack出来る気がしなかった。