Problem 126 「直方体層」 †

3 x 2 x 1 の直方体の表面全てを覆いつくすのに必要最小限の立方体の数は 22 個である.

p_126.gif
さらにこの立体に表面を覆いつくすように2層目を追加すると, 46 個の立方体が必要である. 3層目は 78 個, 4層目は 118 個の立方体が表面を覆いつくすのに必要である.

ところで 5 x 1 x 1 の直方体への1層目も 22 個の立方体が必要である. 同様に 5 x 3 x 1, 7 x 2 x 1, 11 x 1 x 1 の直方体への1層目も全て 46 個の立方体である.

何層目かが n 個の立方体からなる直方体の数を, C(n) と定義する. C(22) = 2, C(46) = 4, C(78) = 5, C(118) = 8 となる.

154 は C(n) = 10 を満たす最小の n であることがわかる.

C(n)=1000 を満たす最小の n を求めよ.
図などの詳細はリンク先参照のこと。



解法
直方体と層を小さいほうから生成していくだけです。
イカの輪切りの要領で平面で輪切りにして考えると各層のブロック数を簡単に計算できます。
計算に1.3秒、優先順位付きキューに30万個くらい要素が入ってるのでもうちょっと賢い方法はありそうです。


#include<stdio.h>
#include<queue>
#include <time.h>

struct E{
	int h,w,d,size,count,p;
	bool operator<(const E& e)const{
		return  count>e.count;
	}
	void calc_count(){
		int body=h*w*2+((size-1)*2+d)*h*2;
		int head1=d*w*2;
		int head2=(w+d)*(size-1)*2*2;
		int head3=((size-1)*(size-2))/2*4*2;
		count=body+head1+head2+head3;
	}
}; 

int main(){
	clock_t start, end;
	start = clock();

	E e,e2;
	e.size=e.h=e.w=e.d=1;
	e.p=0;
	e.calc_count();
	std::priority_queue<E> pq;
	pq.push(e);
	int oldCount=0,sizeCount=0;
	while(pq.empty()==false){
		e=pq.top();
		pq.pop();
		if(e.count!=oldCount&&sizeCount==1000)break;
		if(e.count!=oldCount){
			sizeCount=1;
			oldCount=e.count;
		}else{
			sizeCount++;
		}
		if(e.size==1){
			e2=e;
			if(e2.p==0){
				e2.h++;
				e2.calc_count();
				pq.push(e2);
			}
			e2=e;
			if(e2.p<=1&&e2.h>e2.w){
				e2.p=1;
 				e2.w++;
				e2.calc_count();
				pq.push(e2);
			}
			e2=e;
			if(e2.p<=2&&e2.w>e2.d){
				e2.p=2;
				e2.d++;
				e2.calc_count();
				pq.push(e2);
			}
 		}
		e2=e;
		e2.size++;
		e2.calc_count();
		pq.push(e2);
	}
	printf("ans=%d\n",oldCount);
	end = clock();
 	printf("計算時間: %f秒\n", (double)(end - start) / CLOCKS_PER_SEC);
}