TopCoder SRM 639 Div1 Medium BoardFolding、Div2 Hard BoardFoldingDiv2

解けはしたけど、だいぶ回りくどい解法を取ってしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=13457
http://community.topcoder.com/stat?c=problem_statement&pm=13544

問題

N*Mのグリッドで構成された紙がある。
各セルは白か黒で塗られている。

ここで、紙をセルの境界線を降り線とし、小さい方を大きい方の上に重ねるように折る、という作業を行う。
この時、重ねた部分は上と下の色が一致しなければならない。

折る作業は任意回数行える場合、最終的にあり得る紙の状態数を答えよ。

Div1 MediumではN,Mの最大値が250であり、Div2 Hardは50である。

解法

２つの解法がある。

１つは自分が取った解法で、最後の状態の左上点となりうる点を列挙し、同様に右下となりうる点を列挙し、(左上点, 右下点)の対の数を累積和を使ってO(N^2*M + N*M^2)で求める。

もう一つは、横線を折り線として構成できるパターンと、縦線を折り線として構成できるパターンの積をO(N^2*M + N*M^2)で求める方法である。

計算量は同程度だが、後者の方が実装量が1KB近く小さかったので、ここでは後者を紹介。

以下横線を折り線として構成できるパターン数の計算方法を示す。
縦線については全体を90度回転して同じ処理を繰り返せばよい。
まずO(N^2 * M)の計算量を掛け、２つの行の組が重ねられるかどうかを判定しておく。

次に、DPの要領で上端をY1行、下端をY2行にするような折り方ができるか求めていく。
このDPは折った後の高さが大きい順に処理していき、上端がY1より小さい、または下端がY2より大きいケースから１回折って上端をY1行、下端をY2行に出来るかを求めていけば良い。

int same[260][260],ok[260][260];

class BoardFolding {
	public:
	int paper[500][500];
	
	int ton(char a) {
		if(a>='0' && a<='9') return a-'0';
		if(a>='a' && a<='z') return a-'a'+10;
		if(a>='A' && a<='Z') return a-'A'+36;
		if(a=='#') return 62;
		if(a=='@') return 63;
		return 0;
	}
	
	int dodo(int N,int M) {
		int y1,y2,y,x,h;
		ZERO(same);
		FOR(y1,N) for(y2=y1+1;y2<N;y2++) {
			same[y1][y2]=1;
			FOR(x,M) same[y1][y2] &= paper[y1][x]==paper[y2][x];
		}
		int num=1;
		ZERO(ok);
		ok[0][N-1]=1;
		for(h=N-1;h>=1;h--) FOR(y1,N) {
			y2=y1+h-1;
			if(y2>=N) continue;
			ok[y1][y2]=0;
			for(y=y1-1;y>=0 && ok[y1][y2]==0;y--) {
				if(y1-y>y2-y1+1) break;
				if(same[y][y1+(y1-y-1)]==0) break;
				ok[y1][y2] |= ok[y][y2];
			}
			for(y=y2+1;y<N && ok[y1][y2]==0;y++) {
				if(y-y2>y2-y1+1) break;
				if(same[y2-(y-y2-1)][y]==0) break;
				ok[y1][y2] |= ok[y1][y];
			}
			num += ok[y1][y2];
		}
		return num;
	}
	
	int howMany(int N, int M, vector <string> compressedPaper) {
		int y,x;
		FOR(y,N) FOR(x,M) paper[y][x]=(ton(compressedPaper[y][x/6])>>(x%6))%2;
		int res = dodo(N,M);
		FOR(y,N) FOR(x,M) paper[x][y]=(ton(compressedPaper[y][x/6])>>(x%6))%2;
		return res*dodo(M,N);
	}
}

まとめ

自分の解法もよく頑張って書いたと思ったのに、こんなあっさり書けてしまうのか。