TopCoder SRM 572 Div1 Easy NewArenaPassword

さてSRM572。
Mediumを微妙にTLEしてしまったため、Easyのみの正解ということでランク微増。
まぁEasyをミスらなくてよかった。
http://community.topcoder.com/stat?c=problem_statement&pm=12386

問題

文字列と、文字列長以下の数値Kが与えられる。
この文字列を変形し、先頭K文字と後半K文字が一致するようにしたい。
変更しなければいけない文字数を答える。

解法

本番中、いったん「これグラフの最小コストとかUnion-find使う？」とか迷ったけど、Easyでそんなの必要ないよな…と思いとどまった。
結果的にはこれらで解いてる人もいたようだけど。

幸い、本番中にもう少し楽な考え方が思いついた。
Kが文字列長の半分以下なら、先頭K文字と後半K文字の位置は重複しないので異なる文字の数をカウントするだけで良い。
Kが文字列長に一致するなら、何も変えなくて良い。

問題は、Kが文字列長の半分より大きく文字列長より小さい場合。
この場合先頭K文字と後半K文字がオーバーラップする。

ここで、文字列が"abcdefg"でK=5の場合を考えてみる。先頭の５文字と後半５文字を一致させるということは以下の２つの文字列が一致しないといけないわけだが、

abcde--

• • cdefg

ここで、1文字目と3文字目が一致し、3文字目と5文字目が一致し…と考えると、結局奇数番目の文字はすべて同じになり、偶数番目の文字はすべて同じにならなければいけない。

XYXYX--

• • XYXYX

同様にN文字の文字列の先頭・末尾K文字を一致させるには、(N-K)個の間隔で同じ文字が並ばなければいけない。
後は、1～(N-K-1)文字目を先頭として(N-K)個の間隔で文字を一致させる場合の最小値を求めればよい。
文字列が短いので、"a"～"z"の全通りを試して最小値を求めるだけでいい。

class NewArenaPassword {
	int L;
	public:
	
	int dodo(string s,int K) {
		int i,n=0;
		FOR(i,K) if(s[i]!=s[L-K+i]) n++;
		return n;
	}
	
	int add(string S, int cur,int K) {
		int mi=1000,i,j;
		char c;
		for(c='a';c<='z';c++) {
			j=0;
			for(i=cur;i<L;i+=L-K) if(S[i]!=c) j++;
			mi=min(mi,j);
		}
		return mi;
		
		
	}
	
	int minChange(string oldPassword, int K) {
		L=oldPassword.size();
		
		if(L==K) return 0;
		if(K*2<=L) return dodo(oldPassword,K);
		
		int n=0,i;
		FOR(i,L-K) {
			n += add(oldPassword,i,K);
		}
		return n;
	}
};

まとめ

気づいてしまえば結構簡単に解ける問題。
本番でうまく思いつけて良かった…。