SRM 209 DIV1 Hard CaseysArt

問題 Editorial

問題

□□
□

という形のブロックが無限にある。ブロックは自由に(90度単位で)回転できる。
length*widthの長方形にぴったり詰め込みたい(空白の部分があってはいけない)。
その「場合の数」を答えよ。ただし、対称の形でも別に数える

• 1 <= length <= 18
• 1 <= width <= 15
• 返り値はdouble型。1e-9の相対誤差を含んでも良い

解答

一列覚えるDP。(y座標, x座標, 前(width+1)個の状態)
そのままではメモリが足りないのでy座標の部分を2つだけ覚えるようにする

コメント

書いたものが一発で動いてびっくりした。
しかしメモリが足りなかったので普通の再帰から書きなおした。でもコピペしてyの部分を&1してループを逆順からやるだけなので、簡単だった。
この形には慣れることが出来たといえるだろう。

コード

#include <vector>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long double ld;

ld dp[2][15][1<<16];	//long doubleの意味は無いと思う
struct CaseysArt {
	int h, w;
	double howManyWays(int length, int width) {
		h = length, w = width;
		mset(dp, -1);
		for(int i = h-1; i >= 0; i --) for(int j = w-1; j >= 0; j --) rep(mask, 1<<(w+1)) {
			ld r = 0;
			int nmask = mask >> 1;
			int ni = j+1 == w ? i+1 : i, nj = j+1 == w ? 0 : j+1;
			if(mask&1) {
				if(i == h-1 && j == w-1) {
					r = nmask == 0;
				}else {
					r += dp[ni&1][nj][nmask];
				}
			}else {
				if(i+1 < h && j+1 < w && (~nmask&(1<<(w-1))))
					r += dp[ni&1][nj][nmask | (1 << (w-1)) | (1 << w)];
				if(i+1 < h && j-1 >=0 && (~nmask&(1<<(w-2))) && (~nmask&(1<<(w-1))))
					r += dp[ni&1][nj][nmask | (1 << (w-2)) | (1 << (w-1))];
				if(j+1 < w && ~mask&2) {
					int nmask2 = mask >> 2;
					int ni2 = j+2 == w ? i+1 : i, nj2 = j+2 == w ? 0 : j+2;
					if(i+1 < h && (~nmask2&(1<<(w-2))))
						r += dp[ni2&1][nj2][nmask2 | (1 << (w-2))];
					if(i+1 < h && (~nmask2&(1<<(w-1))))
						r += dp[ni2&1][nj2][nmask2 | (1 << (w-1))];
				}
			}
			dp[i&1][j][mask] = r;
		}
		return dp[0][0][0];
	}
};