TopCoder SRM 831 : Div1 Hard JumpyCheckers

すいません…。
https://community.topcoder.com/stat?c=problem_statement&pm=17627

問題

正整数R,Cが与えられる。
R*Cのチェス盤を考える。左上角は黒マスになっている。

黒マスのうち、いくつかのマスに駒を置くとき、以下を満たす状態は何通りか。

• 斜め45度方向に並んだ3マスを順にマス１・２・３としたとき、マス１・２にコマがあり3にコマがないような配置が1か所以上ある。

解法

以下の解法・コードは最悪ケースで5秒ぐらいかかるので注意。

条件を満たす配置が1個もないようなものを数え上げ、(2^(黒マス数))から引くことを考える。
上2行の黒マスの埋まり具合をbitmaskで保持して置くと、次の行の埋め方はある程度制限される。
それらを総当たりしていこう。
以下のコードは、count_slow関数の方で計算しており、O(R*2^C*3^C)である。
(実際はR*2^(C/2)*3^(C/2)程度なので5秒で済む)
本番はcount_slowで求めた結果をテーブルとして埋め込んで結果通った。

考えたら、1行分を一気に決めるのではなく、1マスずつ決めて行けば普通にO(R*2^C)で収まるなこれ。

ll from[1<<10][1<<10];
ll to[1<<10][1<<10];

const ll mo=1000000007;
class JumpyCheckers {
	public:
	int count(int R, int C) {
		int r,c;
		//for(r=1;r<=20;r++) for(c=1;c<=20;c++) cout<<r<<" "<<c<<" "<<count_slow(r,c)<<endl;
		int ret[21][21]={};
		ret[3][1]=0;
		ret[3][2]=0;
		ret[3][3]=12;
		ret[3][4]=24;
		ret[3][5]=156;
                (略)
		ret[20][19]=562079871;
		ret[20][20]=421573493;
		for(r=1;r<=20;r++) for(c=1;c<=20;c++) assert(ret[r][c]==ret[c][r]);
		return ret[R][C];
		
	}
	int count_slow(int R, int C) {
		int W[2]={(C+1)/2,C/2};
		ZERO(from);
		from[0][0]=1;
		int y,x;
		int sum=0;
		int mask1,mask2,mask3;
		int i;
		FOR(y,R) {
			sum+=W[y%2];
			ZERO(to);
			
			if(y%2==0) {
				int cnt1=0,cnt2=0;
				FOR(mask1,1<<W[0]) FOR(mask2,1<<W[1]) {
					int n0=0;
					int n1=0;
					FOR(x,W[0]) {
						if(mask1&(1<<x)) {
							if(y>=2) {
								if(mask2&(1<<x)) n1|=1<<(x+1);
								if(x&&(mask2&(1<<(x-1)))) n1|=1<<(x-1);
							}
						}
						else {
							if(mask2&(1<<x)) n0|=1<<(x+1);
							if(x&&(mask2&(1<<(x-1)))) n0|=1<<(x-1);
						}
					}
					n0&=(1<<W[0])-1;
					n1&=(1<<W[0])-1;
					if(n0&n1) continue;
					int nm=n0^((1<<W[0])-1);
					cnt1++;
					for(int mask3=nm;mask3>=0;mask3--) {
						mask3&=nm;
						if(n1&~mask3) continue;
						cnt2++;
						(to[mask1][mask2]+=from[mask3][mask2]);
					}
				}
			}
			else {
				FOR(mask1,1<<W[1]) FOR(mask2,1<<W[0]) {
					int n0=0;
					int n1=0;
					FOR(x,W[1]) {
						if(mask1&(1<<x)) {
							if(y>=2) {
								if(mask2&(1<<(x+1))) n1|=1<<(x+1);
								if(x&&(mask2&(1<<x))) n1|=1<<(x-1);
							}
						}
						else {
							if(mask2&(1<<(x+1))) n0|=1<<(x+1);
							if(x&&(mask2&(1<<x))) n0|=1<<(x-1);
						}
					}
					n0&=(1<<W[1])-1;
					n1&=(1<<W[1])-1;
					if(n0&n1) continue;
					int nm=n0^((1<<W[1])-1);
					for(int mask3=nm;mask3>=0;mask3--) {
						mask3&=nm;
						if(n1&~mask3) continue;
						(to[mask2][mask1]+=from[mask2][mask3]);
					}
				}
			}
			
			FOR(mask1,1<<10) FOR(mask2,1<<10) from[mask1][mask2]=to[mask1][mask2]%mo;
			
			
		}
		
		ll ret=1;
		FOR(i,sum) ret=ret*2%mo;
		FOR(mask1,1<<((C+1)/2)) FOR(mask2,1<<((C+1)/2)) ret-=from[mask1][mask2];
		ret=(ret%mo+mo)%mo;
		return ret;
		
	}
}

まとめ

R,Cがもう少し大きければ埋め込み防止できたのかな。