SRM 297 DIV1 Hard DynamiteBoxes

問題 Editorial

問題

箱を2*2*heightに積む。
それぞれの箱は独立に、0.5の確率でダイナマイトが入っていて、そうでなければ空である。
「ダイナマイトクラスター」とはダイナマイトの入った箱の集合で、連結なものである(面でのみ接しているとみなす)。
サイズがdangerousClusterSize以上であるダイナマイトクラスターを含む確率を求めよ

• 1 <= height <= 30
• 1 <= dangerousClusterSize <= 121

解答

DP。まず、2*2なので、各段ごとに最大でも2つの独立のクラスターしか関係しないことに注意する。
なので(高さ * 前の段の状態bitmask * 前の段のクラスターサイズ1 * 前の段のクラスターサイズ2)というふうな状態でできる。
さて、この状態の漸化式を書かなければいけない。
無理やりサイズの状態を2つにしたことによってそれが複雑になってしまう。
自分は(前のmask,今のmask)ごとの((サイズ2つ,1)→サイズ2つ)の行列を前計算(それが複雑に！)したが、実際には上手く場合分けするのもいいのではないかと思う。
あるいは、rng_58さんのコードのように、存在フラグとconnectサイズを4つ全部に持つ状態で、それをmapでやれば簡単で、これが最良なのではないかと思う

コメント

コード

割と汚く長い

#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))

using namespace std;

struct UnionFind {
	vector<int> data;
	UnionFind(int size_) : data(size_, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

struct DynamiteBoxes {
	double getProbability(int height, int dangerousClusterSize) {
		static int nsizetable[1<<4][1<<4][2][6];
		rep(mask, 1<<4) rep(nmask, 1<<4) rep(connected, 2) {
			mset(nsizetable[mask][nmask][connected], 0);
			int *mat = nsizetable[mask][nmask][connected];
			UnionFind uf(8), uf2(4);
			rep(i, 4) if(nmask >> i & 1)
				rep(j, 4) if(i != j && (nmask >> j & 1) && j != 3 - i) uf.unionSet(i, j);
			rep(i, 4) if(mask >> i & 1)
				rep(j, 4) if(i != j && (mask >> j & 1) && (connected || j != 3 - i))
					uf.unionSet(4+i, 4+j), uf2.unionSet(i, j);
			rep(i, 4) if((nmask >> i & 1) && (mask >> i & 1)) uf.unionSet(i, 4+i);
			rep(i, 4) if(nmask >> i & 1) reu(j, i+1, 4) if(nmask >> j & 1)
			if(!uf.findSet(i, j)) {
				//新たなものはconnectedでない
				rep(k, 4) if(uf.findSet(i, k)) mat[2] ++;
				rep(k, 4) if(uf.findSet(j, k)) mat[5] ++;
				rep(i2, 4) if(mask >> i2 & 1) reu(j2, i2+1, 4) if(mask >> j2 & 1)
				if(!uf2.findSet(i2, j2)) {
					if(uf.findSet(i, 4+i2)) mat[0] = 1;
					if(uf.findSet(j, 4+j2)) mat[4] = 1;
					goto next;
				}
				rep(i2, 4) if(uf.findSet(i, 4+i2))
					mat[0] = 1;
				rep(i2, 4) if(uf.findSet(j, 4+i2))
					mat[3] = 1;
				goto next;
			}
			//新たなものはconnected
			rep(i, 4) if(nmask >> i & 1) mat[2] ++;
			rep(i, 4) if(nmask >> i & 1) {
				rep(i2, 4) if(mask >> i2 & 1) reu(j2, i2+1, 4) if(mask >> j2 & 1)
				if(!uf2.findSet(i2, j2)) {
					if(uf.findSet(i, 4+i2)) mat[0] = 1;
					if(uf.findSet(i, 4+j2)) mat[1] = 1;
					goto next;
				}
				rep(i2, 4) if(mask >> i2 & 1) if(uf.findSet(4+i2, i))
					mat[0] = 1;
			}
			next:;
		}
		//高さ, 前の状態, 繋がりサイズ1, 繋がりサイズ2
		static double dp[31][1<<4][122][122];
		mset(dp, 0);
		dp[0][0][0][0] = 1;
		//size1: top left, size2: bottom right
		rep(h, height) rep(mask, 1 << 4)
		rer(size1, 0, dangerousClusterSize) rer(size2, 0, dangerousClusterSize)
		if(double tmp = dp[h][mask][size1][size2]) {
			tmp /= 16;
			if(size1 == dangerousClusterSize || size2 == dangerousClusterSize) {
				rep(nmask, 1<<4) dp[h+1][nmask][dangerousClusterSize][dangerousClusterSize] += tmp;
			}else {
				rep(nmask, 1<<4) {
					int *mat = nsizetable[mask][nmask][size2==0];
					dp[h+1][nmask]
						[min(dangerousClusterSize, mat[0]*size1+mat[1]*size2+mat[2])]
						[min(dangerousClusterSize, mat[3]*size1+mat[4]*size2+mat[5])] += tmp;
				}
			}
		}
		double r = 0;
		for(int mask = 0; mask < 1<<4; mask ++)
		for(int size1 = 0; size1 <= dangerousClusterSize; size1 ++)
		for(int size2 = 0; size2 <= dangerousClusterSize; size2 ++) {
			if(size1 == dangerousClusterSize || size2 == dangerousClusterSize)
				r += dp[height][mask][size1][size2];
		}
		return r;
	}
};