TopCoder SRM 504 Div1 Medium AlgridTwo

Div2 Hardと問題設定の微妙な違いが面白い。
http://community.topcoder.com/stat?c=problem_statement&pm=11355

問題

先のDiv2Hardと元の問題設定は同じである。
TopCoder SRM 504 Div2 Hard Algrid - kmjp's blog

ただ、Div2 Hardは最終的な状態を示す元グリッド状態を１つ挙げるのに対し、こちらは元グリッド状態の候補数を返す。

解法

今回はグリッドサイズN<=50なのでO(2^N)のコードは使えない。

Div2 Hardでは(i+1)行目の内容からi行目の内容を求めたが、今回は逆にi行目の内容から(i+1)行目を求めていく。
(i+1)行目の内容を仮置きした状態で色の切り替えを行っていく。
その際、途中で塗りつぶされてしまうマスはもともと何色でも構わないので、その都度答えは倍々になっていく。

ll mo=1000000007;

class AlgridTwo {
	public:
	ll dodo(string A,string B) {
		int W=A.size(),x;
		string C=string(W,'*');
		
		ll ret=1;
		FOR(x,W-1) {
			if(A[x]=='B' && A[x+1]=='W') {
				if(C[x]=='*') ret<<=1;
				if(C[x+1]=='*') ret<<=1;
				C[x]=C[x+1]='B';
			}
			if(A[x]=='W' && A[x+1]=='B') {
				if(C[x]=='*') ret<<=1;
				if(C[x+1]=='*') ret<<=1;
				C[x]=C[x+1]='W';
			}
			if(A[x]=='B' && A[x+1]=='B') swap(C[x],C[x+1]);
		}
		
		FOR(x,W) if(C[x]!='*' && C[x]!=B[x]) ret=0;
		return ret%mo;
	}
	
	int makeProgram(vector <string> output) {
		int y;
		ll ret=1;
		FOR(y,output.size()-1) ret=ret*dodo(output[y],output[y+1])%mo;
		return (int)ret;
	}
}

まとめ

Div1 Mediumだけどこれはすんなり解けた。