kmjp's blog

競技プログラミング参加記です

天下一プログラマーコンテスト2014 予選B : D - 天下一芸術

なかなか面白い問題だった。
http://tenka1-2014-qualb.contest.atcoder.jp/tasks/tenka1_2014_qualB_d

問題

N色のペンキがあり、それぞれの濃度が与えられる。
濃度が薄い色のペンキに濃い色のペンキを上書きすることはできるが、同じ濃度または薄い濃度で上書きすることはできない。

ここで、HxWのグリッドがあり、各セルに番号が指定される。
同じ番号のセルは同じ色のペンキで塗られなければならず、異なる番号のセルが同じ色のペンキであってはならない。

なお、各色のペンキは任意の順で塗ることができるが、それぞれ1回しか塗ることができず、かつ長方形領域を塗りつぶす形でしか塗ることができない。
指定された番号の通りに色を塗ることができるか答えよ。

解法

まず番号とペンキの色の対応は置いておいて、各番号で塗る範囲を考える。
これは明確で、グリッド上で登場する最左・最右・最上・最下のセルを囲う長方形である。

ここで、上記長方形の範囲の中に他の番号が登場する場合、その番号の方が濃いペンキで後に塗らなければいけないことがわかる。
すなわち番号間の濃度の関係がわかる。

部分点解法

ペンキの種類は高々9個なので、番号とペンキの対応をnext_permutationで総当たりし、上記番号間の濃度関係に違反しないかチェックすればよい。
総当たりがN!、チェックがN^2なので、全体でO(N^2*N!)程度ということで何とか間に合う。

満点解法

ペンキの濃度を昇順ソートし、薄い順に、ただし同じ濃度のペンキが複数あればその数だけまとめてBitDPの容量で番号と色の対応をつけていく。
割り当て済みの番号に対し、新規に割り当てる番号が濃度順で薄いものが無いようにBitDPする。
O(2^N)かO(3^N)程度で解答可能。

int N,A[30];
int H,W;
int BB[300][300],BB2[300][300];
int L[300],R[300],T[300],B[300];
vector<int> V,MA[18];

int mat[20],late[20];
int dpdp[20][1<<19],ms[1<<18];

void solve() {
	int f,i,j,k,l,x,y,mask,mask2;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	V.push_back(1);
	for(i=1;i<N;i++) {
		if(A[i]==A[i-1]) V.back()++;
		else V.push_back(1);
	}
	
	FOR(i,N) L[i]=T[i]=301,R[i]=B[i]=-1;
	cin>>H>>W;
	
	FOR(y,H) FOR(x,W) {
		cin>>BB[y][x];
		i=BB[y][x];
		L[i]=min(L[i],x);
		R[i]=max(R[i],x);
		T[i]=min(T[i],y);
		B[i]=max(B[i],y);
	}
	FOR(i,N) for(y=T[i];y<=B[i];y++) for(x=L[i];x<=R[i];x++) if(BB[y][x]!=i) mat[BB[y][x]] |= 1<<i;
	
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x] |= ((mat[x]>>i)&(mat[i]>>y)&1)<<y;
	FOR(i,N) if(mat[i] & (1<<i)) return _P("0\n");
	FOR(mask2,1<<N) FOR(x,N) if(mask2&(1<<x)) ms[mask2]|=mat[x];
	FOR(mask,1<<N) MA[__builtin_popcount(mask)].push_back(mask);
	
	dpdp[0][0]=1;
	FOR(i,V.size()) {
		FOR(mask,1<<N) if(dpdp[i][mask]) {
			FOR(j,MA[V[i]].size()) {
				mask2=MA[V[i]][j];
				if((mask&mask2)==0 && (ms[mask2]&mask)==ms[mask2] && (ms[mask2]&mask2)==0) dpdp[i+1][mask|mask2]=1;
			}
		}
	}
	cout << dpdp[V.size()][(1<<N)-1] << endl;
}

まとめ

本番時間切れでN<=5の部分点どまりだったが、N<=9の部分点までは行けたな…。
BitDPが思い浮かばなかったので満点は無理だったか。