体調はいまいちだがなぜか出来は良かった。
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出来る気がしなかった。