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

「プロジェクトオイラー問い11～20」(2012/12/14 (金) 18:33:54) の最新版変更点

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

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

*問い11
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011
与えられた20*20の数字表の中から連続する４つの数字を縦横斜めで掛けた時、４つの数字の最大値を見つける問題。

解法
与えられた数字表に０以下の数がないこと、それと縦横斜めの計算をマトリックス化して少しコードを短くしてみました。
もし数字表が数万*数万以上になるとオンメモリにするわけにもいきません。
この場合きちんと処理できるようハードディスクからデータを取り出す関数が必要になります。


 #include<stdio.h>
 int map[20][20];
 int toRe(int y,int x){
	if(y<0||y>19||x<0||x>19)return 0;
	return map[y][x];
 }
 int main(){
	int ans=0,t;
	int dxs[4]={-1,-1,0,1},dys[4]={0,-1,-1,-1};
	for(int y=0;y<20;y++){
		for(int x=0;x<20;x++){
			scanf("%d",&map[y][x]);
			for(int k=0;k<4;k++){
				t=toRe(y,x)*toRe(y+dys[k],x+dxs[k])*toRe(y+2*dys[k],x+2*dxs[k])*toRe(y+3*dys[k],x+3*dxs[k]);
				if(t>ans)ans=t;
			}
		}
	}
	printf("%d\n",ans);
 }












*問い12
三角数の約数の個数が５００個以上になる最小の数を求めよという問題。
解法
答えはm=(n*(n+1))/2の約数の個数となります。
nとｎ+1は互いに素なので約数の個数を求める関数をf(m)とするとf(m)=f(n/2)f(n+1)かf(m)=f((n+1)/2)f(n)となります。
簡単ですね。



 #include<stdio.h>
 int calc(int n){
	int ans=1;
	int num=n%2==0?n/2:n;
	for(int i=2;i*i<=num;i+=(i&1)+1){
		int count=0;
		while(num%i==0){
			num/=i;
			count++;
		}
		ans*=(count+1);
	}
	if(num!=1)ans*=2;
	num=(n+1)%2==0?(n+1)/2:n+1;
	for(int i=2;i*i<=num;i+=(i&1)+1){
		int count=0;
		while(num%i==0){
			num/=i;
			count++;
		}
		ans*=(count+1);
	}
	if(num!=1)ans*=2;
	return ans;
 }
 int main(){
	int n;
	for(n=1;calc(n)<500;n++);
	printf("%d",(n*(n+1))/2);
 }




*問い13
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2013
５０桁の数字１００個が与えられるのでこれの和を求め上位１０ケタを答えよ。

言語によっては多倍張整数ライブラリか自前の実装が必要ですがLisp系統の言語なら+演算子一つで片が付きます。
計算で出てきた数字の上位１０ケタをコピーすれば答えが出ます。

 (+
 37107287533902102798797998220837590246510135740250
 ,,,データなので省略。
 53503534226472524250874054075591789781264330331690)



























*問い14
正の整数に以下の式で繰り返し生成する数列を定義する.
n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)
13からはじめるとこの数列は以下のようになる.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい


解法
メモ化で少しだけ速度を出しつつ地道に計算してみました。
コラッツ問題は再帰を使えばメモ化がスムーズに働き計算量は落ちますが、再帰関数を呼び出すコストが上がりますしスタックオーバーフローの可能性も出てきます。
その辺を取って地道な関数で解いてみました。



 #include<stdio.h>
 #include<iostream>
 const int up=1000*1000;
 int memo[up+1]={0,1,0};
 int main(){
	__int64 num;
	int count,ansLen=0,ansNum;
	for(int i=2;i<up;i++){
		num=i;
		count=0;
		while(num>=i){
			num=num%2==0?num/2:num*3+1;
			count++;
		}
		memo[i]=count+memo[(int)num];
		if(memo[i]>ansLen){
			ansLen=memo[i];
			ansNum=i;
		}
	}
	std::cout<<ansNum<<" "<<ansLen;
 }







*問い15
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015
2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.

*解法
答えは40C20なので電卓でちょちょいでもいいのですがそれでは楽しくありません。
メモ化計算も悪くないのですが、コードで遊ぼうと思ってコンバインで実装してみました。


 #include<stdio.h>
 #include<iostream>
 #include<map>
 #include<math.h>
 std::map<int,int> calc(int down,int up){
	std::map<int,int> re;
	for(int i=down;i<=up;i++){
		int num=i;
		for(int j=2;j<=num;j++){
			int count=0;
			while(num%j==0){
				num/=j;
				count++;
			}
			if(count>0){
				if(re.find(j)==re.end())re[j]=0;
				re[j]+=count;
			}
		}
	}
	return re;
 }
 __int64 combin(int n,int r){
	std::map<int,int> m1,m2;
	std::map<int,int>::iterator it;
	m1=calc(n-r+1,n);
	m2=calc(1,r);
	int u,k;
	__int64 ans=1;
	for(it=m1.begin();it!=m1.end();it++){
		u=(*it).first;
		k=(*it).second;
		if(m2.find(u)!=m2.end())k-=m2[u];
		if(k>0)ans*=pow(u,k);
	}
	return ans;
 }
 int main(){
	std::cout<<combin(40,20);
 }











*問い16
2＾1000の各桁の和がいくつになるか答えよ。

解法
C++でもいいのですが処理が面倒です。
簡単に処理できるlispで実装してみました。
２＾１０００を求めてこれを文字列に変換。
ループで一文字ずつ足しこみました。
Lispは苦手。


 (let ((str (format nil "~A" (expt 2 1000))) (ans 0))
   (dotimes (i (length str) ans)
     (setq ans (+ ans (- (char-code (char str i)) 48)))))














*問い17
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

解法
数字から文字列に変換する関数を作って文字列の長さを数えてみました。
変換する数字が小さいのでコードサイズを以下に小さくするかくらいしか工夫するところがありません。
生成される数字が大きくなった場合は文字数を一気に計算する数式に従った別の処理が必要になるはずです。



 #include<stdio.h>
 #include<string>
 #include<iostream>
 std::string nums19[]={ "dammy","one", "two","three", "four", "five", "six", "seven", "eight", "nine", "ten",
				 "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
 std::string num10n[]={ "dammy","dammy","twenty", "thirty", "forty", "fifty",
				 "sixty", "seventy", "eighty", "ninety" };
 std::string toStr(int n){
	std::string str="";
	while(n!=0){
		if(n>=100){
			str+=nums19[n/100]+"hundred";
			n=n%100;
			if(n!=0)str+="and";
		}else if(n>=20){
			str+=num10n[n/10];
			n%=10;
		}else{
			str+=nums19[n];
			break;
		}
	}
	return str;
 }
 int main(){
	int ans=std::string("onethousand").length();
	for(int i=1;i<1000;i++){
		ans+=toStr(i).length();
	}
	std::cout<<ans;
 }
















*問い18
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2018
三角形に並べられた数字表を上から下へ移動しながら足し合わせるとき最大になる経路の合計値を求めよ。

解法
一段ずつの動的計画法でアセプトできます。

 #include<stdio.h>
 int main(){
	int memo[20]={0},a,ans=0;
	for(int i=1;i<=15;i++){
		int next[20]={0};
		for(int j=1;j<=i;j++){
			scanf("%d",&a);
			next[j]=(memo[j-1]>memo[j]?memo[j-1]:memo[j])+a;
		}
		for(int j=1;j<=i;j++){
			memo[j]=next[j];
			if(ans<memo[j])ans=memo[j];
		}
	}
	printf("%d",ans);
 }










*問い19
１９０１年１月１日～２００１年１２月３１日までの間に、月の初めが日曜で始まる月はいくつあるか？

解法
ツェラーの公式で一発です。


 #include<stdio.h>
 int getWeekday(int nYear, int nMonth, int nDay){
    int nWeekday, nTmp;
    if (nMonth == 1 || nMonth == 2) {
        nYear--;
        nMonth += 12;
    }
    nTmp     = nYear/100;
    nWeekday = (nYear + (nYear >> 2) - nTmp + (nTmp >> 2) + (13*nMonth + 8)/5 + nDay) % 7;
    return nWeekday;
 }
 int main(){
	int ans=0;
	for(int y=1901;y<=2000;y++){
		for(int m=1;m<=12;m++){
			if(getWeekday(y,m,1)==0)ans++;
		}
	}
	printf("%d",ans);
 }

*問い11
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011
与えられた20*20の数字表の中から連続する４つの数字を縦横斜めで掛けた時、４つの数字の最大値を見つける問題。

解法
与えられた数字表に０以下の数がないこと、それと縦横斜めの計算をマトリックス化して少しコードを短くしてみました。
もし数字表が数万*数万以上になるとオンメモリにするわけにもいきません。
この場合きちんと処理できるようハードディスクからデータを取り出す関数が必要になります。


 #include<stdio.h>
 int map[20][20];
 int toRe(int y,int x){
	if(y<0||y>19||x<0||x>19)return 0;
	return map[y][x];
 }
 int main(){
	int ans=0,t;
	int dxs[4]={-1,-1,0,1},dys[4]={0,-1,-1,-1};
	for(int y=0;y<20;y++){
		for(int x=0;x<20;x++){
			scanf("%d",&map[y][x]);
			for(int k=0;k<4;k++){
				t=toRe(y,x)*toRe(y+dys[k],x+dxs[k])*toRe(y+2*dys[k],x+2*dxs[k])*toRe(y+3*dys[k],x+3*dxs[k]);
				if(t>ans)ans=t;
			}
		}
	}
	printf("%d\n",ans);
 }












*問い12
三角数の約数の個数が５００個以上になる最小の数を求めよという問題。
解法
答えはm=(n*(n+1))/2の約数の個数となります。
nとｎ+1は互いに素なので約数の個数を求める関数をf(m)とするとf(m)=f(n/2)f(n+1)かf(m)=f((n+1)/2)f(n)となります。
簡単ですね。



 #include<stdio.h>
 int calc(int n){
	int ans=1;
	int num=n%2==0?n/2:n;
	for(int i=2;i*i<=num;i+=(i&1)+1){
		int count=0;
		while(num%i==0){
			num/=i;
			count++;
		}
		ans*=(count+1);
	}
	if(num!=1)ans*=2;
	num=(n+1)%2==0?(n+1)/2:n+1;
	for(int i=2;i*i<=num;i+=(i&1)+1){
		int count=0;
		while(num%i==0){
			num/=i;
			count++;
		}
		ans*=(count+1);
	}
	if(num!=1)ans*=2;
	return ans;
 }
 int main(){
	int n;
	for(n=1;calc(n)<500;n++);
	printf("%d",(n*(n+1))/2);
 }




*問い13
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2013
５０桁の数字１００個が与えられるのでこれの和を求め上位１０ケタを答えよ。

言語によっては多倍張整数ライブラリか自前の実装が必要ですがLisp系統の言語なら+演算子一つで片が付きます。
計算で出てきた数字の上位１０ケタをコピーすれば答えが出ます。

 (+
 37107287533902102798797998220837590246510135740250
 ,,,データなので省略。
 53503534226472524250874054075591789781264330331690)



























*問い14
正の整数に以下の式で繰り返し生成する数列を定義する.
n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)
13からはじめるとこの数列は以下のようになる.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい


解法
メモ化で少しだけ速度を出しつつ地道に計算してみました。
コラッツ問題は再帰を使えばメモ化がスムーズに働き計算量は落ちますが、再帰関数を呼び出すコストが上がりますしスタックオーバーフローの可能性も出てきます。
その辺を取って地道な関数で解いてみました。



 #include<stdio.h>
 #include<iostream>
 const int up=1000*1000;
 int memo[up+1]={0,1,0};
 int main(){
	__int64 num;
	int count,ansLen=0,ansNum;
	for(int i=2;i<up;i++){
		num=i;
		count=0;
		while(num>=i){
			num=num%2==0?num/2:num*3+1;
			count++;
		}
		memo[i]=count+memo[(int)num];
		if(memo[i]>ansLen){
			ansLen=memo[i];
			ansNum=i;
		}
	}
	std::cout<<ansNum<<" "<<ansLen;
 }







*問い15
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015
2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.

*解法
答えは40C20なので電卓でちょちょいでもいいのですがそれでは楽しくありません。
メモ化計算も悪くないのですが、コードで遊ぼうと思ってコンバインで実装してみました。


 #include<stdio.h>
 #include<iostream>
 #include<map>
 #include<math.h>
 std::map<int,int> calc(int down,int up){
	std::map<int,int> re;
	for(int i=down;i<=up;i++){
		int num=i;
		for(int j=2;j<=num;j++){
			int count=0;
			while(num%j==0){
				num/=j;
				count++;
			}
			if(count>0){
				if(re.find(j)==re.end())re[j]=0;
				re[j]+=count;
			}
		}
	}
	return re;
 }
 __int64 combin(int n,int r){
	std::map<int,int> m1,m2;
	std::map<int,int>::iterator it;
	m1=calc(n-r+1,n);
	m2=calc(1,r);
	int u,k;
	__int64 ans=1;
	for(it=m1.begin();it!=m1.end();it++){
		u=(*it).first;
		k=(*it).second;
		if(m2.find(u)!=m2.end())k-=m2[u];
		if(k>0)ans*=pow(u,k);
	}
	return ans;
 }
 int main(){
	std::cout<<combin(40,20);
 }











*問い16
2＾1000の各桁の和がいくつになるか答えよ。

解法
C++でもいいのですが処理が面倒です。
簡単に処理できるlispで実装してみました。
２＾１０００を求めてこれを文字列に変換。
ループで一文字ずつ足しこみました。
Lispは苦手。


 (let ((str (format nil "~A" (expt 2 1000))) (ans 0))
   (dotimes (i (length str) ans)
     (setq ans (+ ans (- (char-code (char str i)) 48)))))














*問い17
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

解法
数字から文字列に変換する関数を作って文字列の長さを数えてみました。
変換する数字が小さいのでコードサイズを以下に小さくするかくらいしか工夫するところがありません。
生成される数字が大きくなった場合は文字数を一気に計算する数式に従った別の処理が必要になるはずです。



 #include<stdio.h>
 #include<string>
 #include<iostream>
 std::string nums19[]={ "dammy","one", "two","three", "four", "five", "six", "seven", "eight", "nine", "ten",
				 "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
 std::string num10n[]={ "dammy","dammy","twenty", "thirty", "forty", "fifty",
				 "sixty", "seventy", "eighty", "ninety" };
 std::string toStr(int n){
	std::string str="";
	while(n!=0){
		if(n>=100){
			str+=nums19[n/100]+"hundred";
			n=n%100;
			if(n!=0)str+="and";
		}else if(n>=20){
			str+=num10n[n/10];
			n%=10;
		}else{
			str+=nums19[n];
			break;
		}
	}
	return str;
 }
 int main(){
	int ans=std::string("onethousand").length();
	for(int i=1;i<1000;i++){
		ans+=toStr(i).length();
	}
	std::cout<<ans;
 }
















*問い18
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2018
三角形に並べられた数字表を上から下へ移動しながら足し合わせるとき最大になる経路の合計値を求めよ。

解法
一段ずつの動的計画法でアセプトできます。

 #include<stdio.h>
 int main(){
	int memo[20]={0},a,ans=0;
	for(int i=1;i<=15;i++){
		int next[20]={0};
		for(int j=1;j<=i;j++){
			scanf("%d",&a);
			next[j]=(memo[j-1]>memo[j]?memo[j-1]:memo[j])+a;
		}
		for(int j=1;j<=i;j++){
			memo[j]=next[j];
			if(ans<memo[j])ans=memo[j];
		}
	}
	printf("%d",ans);
 }










*問い19
１９０１年１月１日～２００１年１２月３１日までの間に、月の初めが日曜で始まる月はいくつあるか？

解法
ツェラーの公式で一発です。


 #include<stdio.h>
 int getWeekday(int nYear, int nMonth, int nDay){
    int nWeekday, nTmp;
    if (nMonth == 1 || nMonth == 2) {
        nYear--;
        nMonth += 12;
    }
    nTmp     = nYear/100;
    nWeekday = (nYear + (nYear >> 2) - nTmp + (nTmp >> 2) + (13*nMonth + 8)/5 + nDay) % 7;
    return nWeekday;
 }
 int main(){
	int ans=0;
	for(int y=1901;y<=2000;y++){
		for(int m=1;m<=12;m++){
			if(getWeekday(y,m,1)==0)ans++;
		}
	}
	printf("%d",ans);
 }







*問い20
100！の各桁の和を求めよ。

解法
賢い方法があるかもしれませんがLispで100！を求め、これを文字列とみて足しこみました。

 (defun fact (n)
  (if (= n 1) 1
    (* n (fact (- n 1)))))
 (let ((str (format nil "~A" (fact 100))) (ans 0))
  (dotimes (i (length str) ans)
    (setq ans (+ ans (- (char-code (char str i)) 48)))))