TopCoder SRM 589 Div2 Medium GearsDiv2

今回Div2 MediumがDiv1 Easyと違うので解いてみよう。
http://community.topcoder.com/stat?c=problem_statement&pm=12732

問題

N個の歯車が円を成すようにかみ合っており、各歯車の回転方向が与えられる。
ここからいくつか歯車を外し、隣り合う歯車が逆向きで回るようにしたい。
外すべき最小の歯車数を答えよ。

解法

円形なのがややこしいが、最初の１個の歯車を外してしまうとあとは円でなく直線状に並んでるとみなせる。
なので、初期状態でうまくかみ合わない歯車があるなら、それを最初に外してしまう。

直線状の歯車では、両端以外の各歯車について両隣のどちらかが同じ向きに回るなら、その歯車を外して残された２つの歯車群に対して最小の外すべき歯車数を求めていけばよい。
今回はメモ化再帰でこの処理を行っている。
O(N^3)で処理できるかな。

class GearsDiv2 {
	public:
	int N;
	map<string,int> M;
	
	int test(string D) {
		int i;
		if(M.find(D)!=M.end()) return M[D];
		
		int j=0;
		FOR(i,D.size()-1) if(D[i]==D[i+1]) j++;
		if(j<=1) return M[D]=j;
		
		int mi=100;
		for(i=1;i<D.size()-1;i++) if(D[i-1]==D[i] || D[i]==D[i+1]) 
				mi=min(mi,1+test(D.substr(0,i))+test(D.substr(i+1)));
		return M[D]=mi;
	}
	
	int getmin(string D) {
		N=D.size();
		M.clear();
		
		int i,j=0;
		FOR(i,D.size()) if(D[i]==D[(i+1)%N]) j++;
		if(j==0) return 0;
		
		int mi=100;
		FOR(i,N) {
			string S;
			FOR(j,N-1) S+=D[(i+1+j)%N];
			mi=min(mi,1+test(S));
		}
		
		return mi;
	}
};

まとめ

なかなか面白い問題。
でも円形にするのは面倒なだけで面白みはさほど感じないかも…。