天下一プログラマーコンテスト2013 予選A : C - 天下一二三パズル

さてC。これはなかなか面白い問題だった。
http://tenka1-2013-quala.contest.atcoder.jp/tasks/tenka1_2013_qualA_c

問題

HxWマスのマス目に1～3の数字を埋めていく。
このとき、同じ行または列に同じ数字が複数ある場合、その間にその数以上のマスが無ければならない。
HとWが与えられたとき、このルールに反しない数字の並べ方の組み合わせ数を答えよ。

解法

SmallはH<=4、W<=4なのでDFSで全マス試せばよい。
また、実は最初の数マスが決まると他のマスの選択肢はほとんどないので、H<=100、W<=100のケースも下記の愚直なDFSで間に合う(ほとんど分岐しない)。

int H,W;
ll pat=0;

int mat[101][101];

void dfs(int y,int x) {
	
	if(x>=W) x=0,y++;
	if(y>=H) {
		pat++;
		return;
	}
	
	int t=mat[y][x];
	//1
	if((y==0||mat[y-1][x]!=1)&&(x==0||mat[y][x-1]!=1)) {
		if(t==0 || t==1) {
			mat[y][x]=1;
			dfs(y,x+1);
			mat[y][x]=t;
		}
	}
	if((y<1||mat[y-1][x]!=2)&&(y<2||mat[y-2][x]!=2)&&
	   (x<1||mat[y][x-1]!=2)&&(x<2||mat[y][x-2]!=2)) {
		if(t==0 || t==2) {
			mat[y][x]=2;
			dfs(y,x+1);
			mat[y][x]=t;
		}
	}
	if((y<1||mat[y-1][x]!=3)&&(y<2||mat[y-2][x]!=3)&&(y<3||mat[y-3][x]!=3)&&
	   (x<1||mat[y][x-1]!=3)&&(x<2||mat[y][x-2]!=3)&&(x<3||mat[y][x-3]!=3)) {
		if(t==0 || t==3) {
			mat[y][x]=3;
			dfs(y,x+1);
			mat[y][x]=t;
		}
	}
	
	
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty,aa[5];
	
	cin>>H>>W;
	dfs(0,0);
	_P("%lld\n",pat);
	
	return;
}

問題はLarge。H,W<=10^6もある。
ここで、どのような法則でマスが埋まるかを考えてみると、実は12131213…と1213の繰り返しになることがわかる。終端だけは231213のように2と3が連続することもあるけど、中央部は1213のみ。
よって中央部はこの４マスの繰り返しになるだけでそれ以外のレパートリーが無い。

周辺部や角だけ気を付ければいいので、以下の様にDFSをやる前に中央部を省略してしまえばよい。

	if(H>12) H=12+H%4;
	if(W>12) W=12+W%4;
	dfs(0,0);

まとめ

気づくまでに時間がかかった。
でも最終的に解けたのは、H<=100、W<=100までを全パターン列挙して計算がすぐに終わること・数があまり増えないことに気づいたのと、紙上で試して1213の法則に気づけたおかげ。