kmjp's blog

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

Bayan 2015 Contest Elimination : D - Towers

本番に解けなかったけど面白かった。
http://contest.bayan.ir/en/contest/elimination_2014/problem/D/

問題

整数N,Mが与えられる。
縦N*横Mのサイズのグリッドに、底面が1*1、高さが1,2,3,...,(N*M)の(N*M)個の直方体ブロックを立てておいていく。
その際、この(N*M)個の直方体ブロックを連結してできる物体の(底面を除く)最小表面積と、それを実現するブロックの並べ方の組み合わせ数を答えよ。

解法

類似の問題は以前TopCoderOpenで出たね。
ただしこちらの方がずっと難しい。
TopCoderOpen 2014 Round2A Easy SixteenBricks - kmjp's blog

自力で解けないのでEditorialを見て回答。
まず、P個の高さが違うブロックを横一列に並べるとき、どのようにするのが表面積が最小が考える。
それは高さが上に凸になるように並べると側面積が最小になる。
その際の左右から見た面積は、P個中最高のブロックの高さ*2である。
この面積の考察は2次元に配置する場合も適用できる。

また、その際の並べ方はP個のブロックを2個目以降大きい順に左右どちらかに並べていくので、2^(P-1)通りである。

次に2次元で考える。仮にN≦Mとしておく。
これらのブロックはできるだけ行と列の数が少ないように並べた方が良いので、正方形に近い並べ方になる。
よって、大きいブロックから順に1*1→1*2→2*2→2*3→…→p*p→p*(p+1)→(p+1)*(p+1)→…となるように並べていく。
ただしpが途中でNに到達すると、後はN*N→N*(N+1)→N*(N+2)→…→N*Mと横方向のみ伸びる。

そのように大きいブロックの塊を大きくしていくときの組み合わせ数を考える。
p*p→p*(p+1)→(p+1)*(p+1)→…と伸ばすときの伸ばし方だが、p*p→p*(p+1)の過程は上下左右どちらに伸ばしてもいいので伸ばす方向は4通り。
(ただしp==Nなら左右しか伸ばせないので2通り)
p*(p+1)→(p+1)*(p+1)の過程は上下左右のうち短い方を伸ばすだけなので上下または左右で2通り。
また、その際上記横1列の並べ方の考察より、p個の並べ方は2^(p-1)通り。
これら4通り・2通りや2^(p-1)通りの組み合わせをどんどん掛け合わせていけば良い。

ll N,M;
ll mo=1000000007;

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	if(N>M) swap(N,M);
	
	
	int h=1,w=1;
	ll area=5*N*M;
	ll left=N*M-1;
	ll po=0;
	while(h<N || w<M) {
		if(h==w && h<N) area+=2*left, left-=h, w++, po+=2+(h-1);
		else if(h==w || h==N) area+=2*left, left-=h, w++, po+=1+(h-1);
		else area+=2*left, left-=w, h++, po+=1+(w-1);
	}
	_P("%lld %lld\n",area,modpow(2,po));
}

まとめ

これは本番思いつかないな。
面白い問題でした。