kmjp's blog

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

Codeforces #195 Div2. E. Vasily the Bear and Painting Square

Codeforces

Div2でありながら、いまだ30名しか解いていないややこしい問題。
Editorialを見て何とか解いた。
http://codeforces.com/contest/336/problem/E

問題

図がややこしいので、元ページを見た方が良い。
数Nに対して、次のような図形を作る。
i=0～Nに対して、(0,2^i),(0,-2^i),(2^i,0),(-2^i,0)のおよび原点の５点を互いに線分で結ぶ(斜めの正方形の辺および対角線を引いた形になる)
さらに、i=0～N-1に対して、(2^i,2^i)、(2^i,-2^i)、(-2^i,-2^i)、(-2^i,2^i)の４点からなる正方形を作る(軸に平行な正方形を引く。対角線は引かない)。

ここから以下の処理をk回行う。
上記線分から３つ選び、三角形を構成するようにし、その中を何らかの色で塗る。
ただし、すでに三角形の中に塗られた領域がある場合、そのような三角形は選べない。

最終的な色の塗り分け方は何通りあるか。

解法

まず、k回の色は異なるものを使えるので、色の違いはk!通り。
色の違いを除くと、どのように三角形をk個選ぶかを計算していく必要がある。
三角形の選び方として、１つの象限からなるものと、２つの象限からなるものがある。

各iについて、一番外側の三角形は12個ある。
第１象限について言えば、(2^(i-1),2^(i-1) ) (2^(i-1),0)(2^i,0)、(0,2^(i-1) )(2^(i-1),2^(i-1) ) (2^(i-1),0)、(0,2^i)(0,2^(i-1) )(2^(i-1),2^(i-1) )と３つある。
先頭の三角形から反時計回りに0～11番と名付けると、ここから三角形を選ぶ方法は以下の方法がある。

  • 0～11番から１つずつ選んでいく
  • 象限をまたぐ２つ組、0-11,2-3,5-6,8-9をとる
  • １象限分全部0-1-2,3-4-5,6-7-8,9-10-11をとる。
  • ２象限分全部0-1-2-3-4-5,3-4-5-6-7-8,6-7-8-9-10-11,9-10-11-0-1-2をとる。

このうち、後ろ二つ、１象限全部または２象限全部とると、以後その象限はより小さいiについて三角形をとることができない。

この事実をもとに、[iの値][残りのkの数][まだ利用できる象限のbitmask]でDPをしていけばよい。
以下のコードでは計算を早くするため、回転して同じになる象限の構成は同一視して計算を省略している。

int N,K;
ll mo=1000000007;
ll dpdp[205][205][16];
const int CN=20;
ll C[CN][CN];

ll dodp(int level,int num,int mask) {
	int ma,i,j,k[5],l;
	if(num==0) return 1;
	if(num<0 || mask==0) return 0;
	if(dpdp[level][num][mask]!=-1) return dpdp[level][num][mask];
	
	ll ret=0;
	FOR(ma,16) {
		if((mask & ma)!=ma) continue;
		
		//get whole block
		int bi=__builtin_popcount(ma);
		k[0]=k[1]=k[2]=k[3]=k[4]=0;
		k[bi]=1;
		if(bi==2 && (ma!=5) && (ma!=10)) k[1]++;
		if(bi==3) k[2]+=2;
		if(bi==4) k[2]+=2,k[3]+=4;
		
		// get boarder
		if(level>0) {
			int ma2=mask^ma;
			if(ma2==13 || ma2==11 || ma2==14) ma2=7;
			if(ma2==9 || ma2==6 || ma2==12) ma2=3;
			if(ma2==10) ma2=5;
			if(ma2==2 || ma2==4 || ma2==8) ma2=1;
			
			int x,y;
			FOR(l,5){
				if(k[l]==0) continue;
				if(num-l<0) continue;
				if(ma2==0) x=0,y=0;
				else if(ma2==1) x=3,y=0;
				else if(ma2==5) x=6,y=0;
				else if(ma2==3) x=6,y=1;
				else if(ma2==7) x=9,y=2;
				else if(ma2==15) x=12,y=4;
				FOR(i,y+1) FOR(j,x-i*2+1) ret += dodp(level-1,num-l-(i+j),ma2) * ((k[l]* C[y][i] * C[x-i*2][j])%mo);
			}
		}
		else {
			FOR(l,5) ret += (num==l) * k[l];
		}
	}
	
	return dpdp[level][num][mask]=(ret%=mo);
}

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N>>K;
	FOR(x,CN) C[x][0]=C[x][x]=1;
	for(i=1;i<CN;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	MINUSL(dpdp);
	
	ll ret=dodp(N,K,15);
	FOR(i,K) ret=(ret*(i+1))%mo;
	cout << ret << endl;
}

まとめ

言われてみれば気づくけど、これを本番中に解ききるのは難しいな。