「プロジェクトオイラー問126」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問126 - (2014/03/09 (日) 04:10:07) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20126
 
 *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秒、優先順位付きキューに30万個くらい要素が入ってるのでもうちょっと賢い方法はありそうです。
+計算に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);
  }