「プロジェクトオイラー問い81～90」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問い81～90」(2013/01/04 (金) 02:38:24) の最新版変更点

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

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

*問い81
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081
80*80サイズの表の左上から出発して表の右下まで進む時、経路上の数字の和が最小になるルートを求めよ。
下か右にしか移動できないものとする。

解法
一段ずつの動的計画法で一発です。

 #include<stdio.h>
 #include<string.h>
 int main(){
 	int ans[81][81],num;
 	char c;
 	memset(ans,0,sizeof(ans));
 	for(int i=1;i<=80;i++){
 		for(int j=1;j<=80;j++){
 			scanf("%d%c",&num,&c);
 			if(i==1){
 				ans[i][j]=num+ans[i][j-1];
 			}else if(j==1){
 				ans[i][j]=num+ans[i-1][j];
 			}else{
 				ans[i][j]=num+(ans[i-1][j]<ans[i][j-1]?ans[i-1][j]:ans[i][j-1]);
 			}
 		}
 	}
 	printf("%d",ans[80][80]);
 }












*問い82
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2082
問い81でスタート地点が左端の列、ゴールが右端の列、途中の経路は右下上の３方向に移動できるという問題です。

解法
この問題は特殊なグラフとみてダイクストラ法で解いてもいいのですが、尺取り虫法と動的計画法を組み合わせて解いてみました。

 #include<stdio.h>
 #include<string.h>
 int main(){
 	int map[81][81],memo[81][81];
 	char c;
 	memset(map,0,sizeof(map));
	memset(memo,0,sizeof(memo));
  	for(int i=1;i<=80;i++){
 		for(int j=1;j<=80;j++){
 			scanf("%d%c",&map[i][j],&c);
 		}
 	}
 	
 	
 	for(int col=1;col<=80;col++){
 		for(int row=1;row<=80;row++)memo[row][col]=memo[row][col-1]+map[row][col];
 		//上から下へ尺取り虫法
 		for(int row=2;row<=80;row++){
 			int num=memo[row-1][col]+map[row][col];
 			if(memo[row][col]>num)memo[row][col]=num;
 		}
 		//下から上へ尺取り虫法
 		for(int row=79;row>=1;row--){
 			int num=memo[row+1][col]+map[row][col];
 			if(memo[row][col]>num)memo[row][col]=num;
 		}
 	}
 	int ans=memo[1][80];
 	for(int row=1;row<=80;row++)if(ans>memo[row][80])ans=memo[row][80];
 	printf("%d",ans);
 }














*問い83
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2083
問い81が上下左右の移動が可能になったもの。

解法 
流石にここら辺まで品雑になると素直にダイクストラ法で実装するのが楽です。

 #include<stdio.h>
 #include<queue>
 
 struct S{
 	int num,row,col;
 	bool operator<(const S& s)const{
 		return num>s.num;//優先順位付きキューで小さい数字から出てくるように計算
 	}
 };
  
 int main(){
 
 	int map[81][81],memo[81][81];
 	std::priority_queue<S> qu;
 	char c;
 	memset(memo,0,sizeof(memo));
  	for(int i=1;i<=80;i++){
  		for(int j=1;j<=80;j++)scanf("%d%c",&map[i][j],&c);
 	}
 	S s,nextS;
 	s.row=s.col=1;
 	s.num=map[1][1];
 	qu.push(s);
 	int dxs[]={1,0,-1,0};
 	int dys[]={0,1,0,-1};
 	while(!qu.empty()){
  		s=qu.top();
 		qu.pop();
 		if(s.row==80&&s.col==80)break;
 		for(int i=0;i<4;i++){
 			int r=s.row+dys[i];
 			int c=s.col+dxs[i];
 			if(r<1||80<r||c<1||80<c)continue;
 			nextS.row=r;
 			nextS.col=c;
 			nextS.num=s.num+map[r][c];
 			if(memo[r][c]!=0&&memo[r][c]<=nextS.num)continue;
 			map[r][c]=nextS.num;
 			qu.push(nextS);
 		}
 		int t;
 	}
 	printf("%d",s.num);
 }


















*問い87
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2087
５０００万以下の数で素数の２乗+素数の３乗+素数の４乗で表現できる数はいくつあるか？

解法
２乗、３乗、４乗は密度が低いので全ての組み合わせを試しても十分間に合います。

 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<set>
 const int up=10000;
 std::vector<__int64> sosuu2,sosuu3,sosuu4;
 std::set<int> memo;
 bool so[up+1];
 void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	so[0]=so[1]=false;
 	for(int i=4;i<=up;i+=2)so[i]=false;
 	sosuu2.push_back(4);
 	sosuu3.push_back(8);
 	sosuu4.push_back(16);
  	for(int i=3;i<=up;i+=2){
 		if(so[i]==false)continue;
 		if(i<7072)sosuu2.push_back(i*i);
 		if(i<369)sosuu3.push_back(i*i*i);
  		if(i<85)sosuu4.push_back(i*i*i*i);
 		i2=i*2;
 		for(int j=i*3;j<=up;j+=i2){
 			so[j]=false;
 		}
 	}
 }
 int main(){
 	setSo();
 	std::set<int> ans;
 	for(int i=0;i<sosuu2.size();i++){
 		for(int j=0;j<sosuu3.size();j++){
 			for(int k=0;k<sosuu4.size();k++){
 				int sum=sosuu2[i]+sosuu3[j]+sosuu4[k];
 				if(sum<5000*10000)ans.insert(sum);
 			}
 		}
 	}
 	printf("%d",ans.size());
 }

*問い81
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081
80*80サイズの表の左上から出発して表の右下まで進む時、経路上の数字の和が最小になるルートを求めよ。
下か右にしか移動できないものとする。

解法
一段ずつの動的計画法で一発です。

 #include<stdio.h>
 #include<string.h>
 int main(){
 	int ans[81][81],num;
 	char c;
 	memset(ans,0,sizeof(ans));
 	for(int i=1;i<=80;i++){
 		for(int j=1;j<=80;j++){
 			scanf("%d%c",&num,&c);
 			if(i==1){
 				ans[i][j]=num+ans[i][j-1];
 			}else if(j==1){
 				ans[i][j]=num+ans[i-1][j];
 			}else{
 				ans[i][j]=num+(ans[i-1][j]<ans[i][j-1]?ans[i-1][j]:ans[i][j-1]);
 			}
 		}
 	}
 	printf("%d",ans[80][80]);
 }












*問い82
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2082
問い81でスタート地点が左端の列、ゴールが右端の列、途中の経路は右下上の３方向に移動できるという問題です。

解法
この問題は特殊なグラフとみてダイクストラ法で解いてもいいのですが、尺取り虫法と動的計画法を組み合わせて解いてみました。

 #include<stdio.h>
 #include<string.h>
 int main(){
 	int map[81][81],memo[81][81];
 	char c;
 	memset(map,0,sizeof(map));
	memset(memo,0,sizeof(memo));
  	for(int i=1;i<=80;i++){
 		for(int j=1;j<=80;j++){
 			scanf("%d%c",&map[i][j],&c);
 		}
 	}
 	
 	
 	for(int col=1;col<=80;col++){
 		for(int row=1;row<=80;row++)memo[row][col]=memo[row][col-1]+map[row][col];
 		//上から下へ尺取り虫法
 		for(int row=2;row<=80;row++){
 			int num=memo[row-1][col]+map[row][col];
 			if(memo[row][col]>num)memo[row][col]=num;
 		}
 		//下から上へ尺取り虫法
 		for(int row=79;row>=1;row--){
 			int num=memo[row+1][col]+map[row][col];
 			if(memo[row][col]>num)memo[row][col]=num;
 		}
 	}
 	int ans=memo[1][80];
 	for(int row=1;row<=80;row++)if(ans>memo[row][80])ans=memo[row][80];
 	printf("%d",ans);
 }














*問い83
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2083
問い81が上下左右の移動が可能になったもの。

解法 
流石にここら辺まで品雑になると素直にダイクストラ法で実装するのが楽です。

 #include<stdio.h>
 #include<queue>
 
 struct S{
 	int num,row,col;
 	bool operator<(const S& s)const{
 		return num>s.num;//優先順位付きキューで小さい数字から出てくるように計算
 	}
 };
  
 int main(){
 
 	int map[81][81],memo[81][81];
 	std::priority_queue<S> qu;
 	char c;
 	memset(memo,0,sizeof(memo));
  	for(int i=1;i<=80;i++){
  		for(int j=1;j<=80;j++)scanf("%d%c",&map[i][j],&c);
 	}
 	S s,nextS;
 	s.row=s.col=1;
 	s.num=map[1][1];
 	qu.push(s);
 	int dxs[]={1,0,-1,0};
 	int dys[]={0,1,0,-1};
 	while(!qu.empty()){
  		s=qu.top();
 		qu.pop();
 		if(s.row==80&&s.col==80)break;
 		for(int i=0;i<4;i++){
 			int r=s.row+dys[i];
 			int c=s.col+dxs[i];
 			if(r<1||80<r||c<1||80<c)continue;
 			nextS.row=r;
 			nextS.col=c;
 			nextS.num=s.num+map[r][c];
 			if(memo[r][c]!=0&&memo[r][c]<=nextS.num)continue;
 			map[r][c]=nextS.num;
 			qu.push(nextS);
 		}
 		int t;
 	}
 	printf("%d",s.num);
 }

















*問い85
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2085
注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.
ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 一番近い解を持つような格子の面積を求めよ

解法
長方形の縦横をa,bとすると作れる長方形の数はa(a+1)b(b+1)/４個となります。
aが決まれば後はｂに関する２次方程式なのでこれを解くだけです。

 #include<stdio.h>
 #include<math.h>
 int main(){
 	int limit=2000*1000,sa,ans=limit,ansSa=limit;
 	for(double a=1;a*(a+1)*a*(a+1)<=limit*4;a+=1){
 		int b=(-1.0+sqrt(1.0+4.0*limit*4.0/(a*a+a)))/2.0;
 		int m=(a*(a+1)*b*(b+1))/4;
 		sa=m-limit;
 		if(sa<0)sa=-sa;
 		if(ansSa>sa){
 			ansSa=sa;
 			ans=a*b;
 		}
 		m=(a*(a+1)*(b+1)*(b+2))/4;
 		sa=m-limit;
		if(sa<0)sa=-sa;
 		if(ansSa>sa){
 			ansSa=sa;
 			ans=a*(b+1);
 		}
 	}
 	printf("%d",ans);
 }













*問い87
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2087
５０００万以下の数で素数の２乗+素数の３乗+素数の４乗で表現できる数はいくつあるか？

解法
２乗、３乗、４乗は密度が低いので全ての組み合わせを試しても十分間に合います。

 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<set>
 const int up=10000;
 std::vector<__int64> sosuu2,sosuu3,sosuu4;
 std::set<int> memo;
 bool so[up+1];
 void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	so[0]=so[1]=false;
 	for(int i=4;i<=up;i+=2)so[i]=false;
 	sosuu2.push_back(4);
 	sosuu3.push_back(8);
 	sosuu4.push_back(16);
  	for(int i=3;i<=up;i+=2){
 		if(so[i]==false)continue;
 		if(i<7072)sosuu2.push_back(i*i);
 		if(i<369)sosuu3.push_back(i*i*i);
  		if(i<85)sosuu4.push_back(i*i*i*i);
 		i2=i*2;
 		for(int j=i*3;j<=up;j+=i2){
 			so[j]=false;
 		}
 	}
 }
 int main(){
 	setSo();
 	std::set<int> ans;
 	for(int i=0;i<sosuu2.size();i++){
 		for(int j=0;j<sosuu3.size();j++){
 			for(int k=0;k<sosuu4.size();k++){
 				int sum=sosuu2[i]+sosuu3[j]+sosuu4[k];
 				if(sum<5000*10000)ans.insert(sum);
 			}
 		}
 	}
 	printf("%d",ans.size());
 }