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

オイラープロジェクト61~70 - (2012/09/02 (日) 05:39:35) の編集履歴(バックアップ)


問い61

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
四角数 P4,n=n2 1, 4, 9, 16, 25, ...
五角数 P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 P6,n=n(2n-1) 1, 6, 15, 28, 45, ...
七角数 P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ...
八角数 P8,n=n(3n-2) 1, 8, 21, 40, 65, ...
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
同じように, 6つの4桁の数からなる順番付きの集合で,
集合は巡回的である
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる 唯一の集合を求め, その和を求めよ.

最初に1000~9999の間の数が何角数であるかをメモ化します。


後は範囲が狭いのでスタートを決めて条件を満たす数を再帰で全探索するだけです。
このときn角数∧m角数であるような数に対処するために探索を分岐するだけです。

#include<stdio.h>
int memo[10000]={0};
int ans[6];
void saiki(int num,int perm,int deep,int ss){
if(deep==6){
	int sum=0;
	if(num==ss&&perm==63){
		for(int i=0;i<6;i++){
			printf("%d ",ans[i]);
			sum+=ans[i];
		}
		printf(" %d\n",sum);
	}
}else{
	int next;
	for(int i=0;i<100;i++){
		next=num+i;
		int p=memo[next];
		for(int k=1;k<=32;k*=2){
			if(((p&k)!=0)&&((perm&k)==0)){
				ans[deep]=next;
				saiki(i*100,perm|k,deep+1,ss);
			}
		}
	}
}
}
int up=10000;
int main(){
int m;
for(int n=1;n<=up;n++){
	m=(n*(n+1))/2;
	if(m<up&&m>999)memo[m]|=1;
	m=n*n;
	if(m<up&&m>999)memo[m]|=2;
	m=(n*(3*n-1))/2;
	if(m<up&&m>999)memo[m]|=4;
	m=n*(2*n-1);
	if(m<up&&m>999)memo[m]|=8;
	m=(n*(5*n-3))/2;
	if(m<up&&m>999)memo[m]|=16;
	m=(n*(3*n-2));
	if(m<up&&m>999)memo[m]|=32;
}
for(int i=10;i<100;i++){
	saiki(i*100,0,0,i*100);
}
}

問い67

http://projecteuler.net/problem=67
三角形に並んだ数字を上から下へ向かいながら途中の経路の計が最高になるルートの合計値を見つけよという問題。
問い18のコードのサイズを少し変更するだけで作成可能。




#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int memo[2][101],a,now,next;
sizeof(memo,0,sizeof(memo));
scanf("%d",&memo[0][0]);
for(int i=1;i<100;i++){
	now =(i+1)%2;
	next=i%2;
	for(int j=0;j<=i;j++){
		scanf("%d",&a);
		if(j==i){
			memo[next][j]=memo[now][j-1]+a;
		}else if(j>0&&j<i){
			memo[next][j]=std::max(memo[now][j-1],memo[now][j])+a;
		}else{
			memo[next][j]=memo[now][j]+a;
		}
	}
}
int ans=0;
for(int i=0;i<100;i++)ans=std::max(ans,memo[next][i]);
printf("%d\n",ans);
}