TopCoder SRM 836 : Div1 Hard BoxWorld

これはなんとか解けてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17798

問題

R*Cのサイズのマス目状のテーブルがある。
ここで、各面がマス目と同じサイズのN個のサイコロを置くことを考える。
各サイコロは、マス目に沿っていずれかのマス目に置くか、すでに置いたサイコロの上に重ねる形で置く。

サイコロの面のうち、テーブルや他のサイコロの面と接していない箇所の総面積を考える。
この総面積が最大となる置き方は何通りか。ただし各サイコロは同一視する。

解法

まず最大となるケースを考える。
サイコロの底面はどうおいても総面積に寄与しない。

サイコロをテーブルの上に直接置くと、その分総面積が増える。すでにあるサイコロの上にサイコロを重ねると、上面分は得しない。
基本的に側面の4面分は常に総面積に寄与するが、もしサイコロを隣のマス目に置いてしまうと、2面分面積を損する。

よって最適手は、隣同士のマスにはサイコロを置かないが、極力多くのマス目にサイコロを置くことである。
サイコロを置くマス目数を定めると、その上にN個のサイコロをどうおくかは重複組み合わせで計算できる。

残るは、サイコロを置くマス目数が最大となるマス目の選び方である。
これは、1行分のサイコロ配置の有無と、これまでサイコロを置いたマス目の数を状態と持つことで、状態数がO(2^C*RC)、それをR*Cマスについて考えるとO((RC)^2*2^C)で解ける。

ll from[1<<14][100];
ll to[1<<14][100];
const ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}


class BoxWorld {
	public:
	int count(int R, int C, int N) {
		ZERO(from);
		int y,x,mask,num;
		FOR(mask,1<<C) if((mask&(mask>>1))==0) from[mask][__builtin_popcount(mask)]++;
		FOR(y,R-1) {
			FOR(x,C) {
				ZERO(to);
				FOR(mask,1<<C) for(num=0;num<=98;num++) if(from[mask][num]) {
					int up=mask&(1<<x);
					int lef=(x==0?0:(mask>>(x-1))&1);
					if(up) {
						to[mask^up][num]+=from[mask][num];
					}
					else {
						to[mask][num]+=from[mask][num];
						if(lef==0) to[mask^(1<<x)][num+1]+=from[mask][num];
					}
				}
				FOR(mask,1<<C) for(num=0;num<=99;num++) from[mask][num]=to[mask][num]%mo;
			}
		}
		for(x=99;x>=0;x--) {
			int ok=0;
			ll ret=0;
			FOR(mask,1<<C) if(x&&x<=N&&from[mask][x]) {
				ok=1;
				ret+=hcomb(x,N-x)*from[mask][x]%mo;
			}
			if(ok) return ret%mo;
		}
		return 0;
	}
}

まとめ

これはしっかり解けてよかったね。