TopCoder SRM 589 Div2 Hard FlippingBitsDiv2

さてDiv2 hard。
http://community.topcoder.com/stat?c=problem_statement&pm=12731

問題

２進数表記の文字列Bと整数Mが与えられる。MはBの長さN(<=2500)の約数である。
Bに対し、以下の処理が行える。

1. 任意の１桁を反転する。
2. 先頭k×M桁を反転する (kは整数)
3. 末尾k×M桁を反転する (kは整数)

Bを全桁1にする場合に必要な最少処理回数を求めよ。

解法

Bをどこかで区切って、そこより前は先頭桁の反転、後ろは末尾桁の反転を使うようにしていく。
そして区切りの前と後それぞれで全桁1にする最小処理数を求めていけばよい。

区切りの前がA×M桁とすると、以下の処理を再帰的に行えばよい

• 末尾M桁中の0の数だけ処理1で1に反転し、残りの(A-1)×M桁を再帰的に処理
• 一旦A×M桁を処理2で反転し、末尾M桁中の0の数だけ処理1で1に反転し、残りの(A-1)×M桁を再帰的に処理

区切りの後ろも同様に行えばよい。
以下のコードでは、区切りの後ろの文字を反転させて同じ関数testを使いまわしている。

class FlippingBitsDiv2 {
	map<string, int> MM;
	int M;
	public:
	
	int test(string SS) {
		if(MM.find(SS)!=MM.end()) return MM[SS];
		if(SS.size()==0) return 0;
		
		int i,t=0;
		FOR(i,M) if(SS[SS.size()-1-i]=='0') t++;
		string SR;
		FOR(i,SS.size()-M) SR += (SS[i]=='0'?'1':'0');
		return MM[SS] = min(t+test(SS.substr(0,SS.size()-M)), 1+M-t+test(SR));
	}
	
	int getmin(vector <string> S, int M) {
		string SS;
		int i,N;
		
		FOR(i,S.size()) SS+=S[i];
		N=SS.size();
		this->M=M;
		
		MM.clear();
		string SR=SS;
		reverse(SR.begin(),SR.end());
		
		int mi=10000;
		for(i=0;i<=N/M;i++) mi=min(mi,test(SS.substr(0,i*M))+test(SR.substr(0,N-i*M)));
		return mi;
		
	}
};

まとめ

これは割と簡単な問題。