TopCoderOpen 2014 Round1A Hard EllysLamps

手間のかかる解法をしてしまったのは反省だが、ともかく解ききれたのはよかった。
http://community.topcoder.com/stat?c=problem_statement&pm=11906

問題

0～(N-1)のランプがあり、初期状態として点灯の有無が与えられる。

ここで各ランプに対応したボタンがあり、それを押すとそのランプのon/offが切り替わる。
ただし、機械の故障でボタンが両隣接ランプと接続されてしまっている可能性がある。

onのランプの数を最少化しようとしたとき、機械の状態によってはonのランプを0に出来ない。
最大何個のランプがonになるか答えよ。

解法

シンプルな解法としては、どうやっても1個onになってしまうパターン("YN","NY","YYY")を何個探せるか、というものがあるようだ。

以下はちょっと時間がかかるけど、自分の解法を紹介。
L番～R番のボタンが互いに故障で隣接ランプに接続されているとする。
その時端からボタンを押していき最少で残る数を求める。

後はL～Rの組を合わせて0～(N-1)全体を構成する組み合わせのうち残るランプ数を最大化するようDPする。
計算量は最初の処理でO(N^3)、DPがO(N^2)。

注意

上記の見解(端からボタンを押していく)は本当は機械の故障の状態が対称でなければ成り立たない。
ただし、結果的にランプ故障最多ケースは"YN","NY","YYY"を含む場合であり、かつそれらでonのランプが残るのは各ボタンが対称に壊れた場合なので正解できる。

class EllysLamps {
	public:
	int wor[51][51];
	int dpdp[51];
	int L;
	string R;
	
	int minmin(int LL,int RR) {
		int ma=10000,i,x,y=0;
		FOR(i,2) {
			string T=R;
			if(T[LL]) {
				if(i==0) T[LL]^=1,T[LL+1]^=1;
				else T[LL]^=1,T[LL+1]^=1,T[LL+2]^=1;
			}
			for(x=LL+2;x<=RR;x++) if(T[x-1]) T[x-1]^=1,T[x]^=1,T[x+1]^=1;
			for(x=LL;x<=RR;x++) y+=T[x];
			ma=min(ma,y);
		}
		return ma;
	}
	
	int getMin(string lamps) {
		int x,y;
		R=lamps;
		L=lamps.size();
		FOR(x,L) R[x]=R[x]=='Y';
		R+='\0'; R+='\0';
		
		ZERO(dpdp);
		FOR(x,L) FOR(y,x+1) dpdp[x+1]=max(dpdp[x+1],dpdp[y]+minmin(y,x));
		return dpdp[L];
	}
};

解法

本番"NY","YN"のケースは1個残るよな…と思いつつ、"YYY"のケースに至れなかった。
結果的には面倒だけどこのアプローチで良かったことになるな。