「オイラー11～20」の編集履歴（バックアップ）一覧に戻る
オイラー11～20 - (2012/08/29 (水) 12:32:12) のソース
*問い11
20*20の表の中から縦横斜め連続した４数を選びその積の最大値を探し出す問題。
動的計画法やメモ化を使おうと思ったら表の中に0が混じってるので0をうまく処理する方法を思いつかず全探索となった。
何か賢い方法あるのかな？
#include<stdio.h>
#include<math.h>
#include<string.h>
int main(){
int map[20][20]={{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
{49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
{81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
{52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
{22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
{24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
{32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
{67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
{24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
{21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
{78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
{16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
{86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
{19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
{ 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
{88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
{ 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
{20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
{20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
{ 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48}};
int ans=0,t,ansR,ansC;
//動的計画法やメモ化を使おうと思ったら表に0が混じってるのでちょっと賢い方法を思いつかない
for(int i=3;i<20;i++){
for(int r=0;r<20;r++){
//横方向
t=map[r][i-3]*map[r][i-2]*map[r][i-1]*map[r][i];
if(ans<t){
ansR=r;
ansC=i;
ans=t;
}
}
for(int c=0;c<20;c++){
//縦方向
t=map[i][c]*map[i-1][c]*map[i-2][c]*map[i-3][c];
if(ans<t){
ansR=i;
ansR=c;
ans=t;
}
}
for(int j=3;j<20;j++){
//左斜め
t=map[i][j]*map[i-1][j-1]*map[i-2][j-2]*map[i-3][j-3];
if(ans<t){
ansR=i;
ansC=j;
ans=t;
}
}
}
for(int c=0;c<17;c++){
for(int r=3;r<20;r++){
t=map[r][c]*map[r-1][c+1]*map[r-2][c+2]*map[r-3][c+3];
if(ans<t){
ansR=r;
ansC=c;
ans=t;
}
}
}
printf("%d %d %d",ans,ansR,ansC);
}
*問い12
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2012
約数が501個を超える最小の三角数を求める問題。
もしかしたら条件を満たすのは恐ろしく大きな数で、非常に高速な約数の個数算出法がいるのかと思ってビビっていた問題。
とりあえず試しに解いてみたら一瞬で答えが出てしまった。
何だか損した気分。
#include<stdio.h>
#include<iostream>
int calc(__int64 n){
int b=1;
while(n%2==0){
b++;
n/=2;
}
for(int i=3;i<=n;i+=2){
int c=1;
while(n%i==0){
n/=i;
c++;
}
b*=c;
}
return b;
}
int main(){
__int64 i=1;
int ans;
while(1){
ans=calc((i*(i+1))/2);
std::cout<<(i*(i+1))/2<<" "<<ans<<"\n";
if(ans>=501)break;
i++;
}
}
＊問い13
５０桁の数を１００個足した後の上位１０ケタの数を求めよという問題。
桁数固定なので手抜き実装でクリア。
#include<stdio.h>
#include<string.h>
#include<algorithm>
void add(char p1[60],char p2[60]){
char a=0;
for(int i=0;i<60;i++){
p1[i]+=p2[i]+a;
a=p1[i]/10;
p1[i]%=10;
}
}
int main(){
char ans[60];
char num[60];
memset(ans,0,sizeof(ans));
memset(num,0,sizeof(num));
for(int i=0;i<100;i++){
scanf("%s",num);
for(int i=0;i<25;i++)std::swap(num[i],num[49-i]);;
for(int i=0;i<50;i++)num[i]-='0';
for(int i=50;i<60;i++)num[i]=0;
add(ans,num);
}
int p;
for(p=59;p>0;p--)if(ans[p]!=0)break;
for(int i=0;i<10;i++)printf("%c",ans[p-i]+'0');
}
*問い14
コラッツ問題の１００万以下の最長数列となる数字を答える問題。
一度ある数になればそれ以降は完全に一本道です。
これを利用してメモ化で解きます。
#include<stdio.h>
#include<iostream>
const int up=1000001;
int memo[up]={0};
int saiki(__int64 num){
if(num==1){
return 1;
}else if(up>num &&memo[(int)num]>0){
return memo[(int)num];
}else{
int k=saiki(num%2==0?num/2:3*num+1)+1;
if(num<up)memo[(int)num]=k;
return k;
}
}
int main(){
int ans=0;
int test[10]={1,8,20,2,16,5,13,4,40,40};
for(int i=0;i<10;i++){
printf("%d ",saiki(test[i]));
}
int no;
for(__int64 i=1;i<up;i++){
int t=saiki(i);
if(ans<t){
ans=t;
no=(int)i;
}
}
std::cout<<ans<<" "<<no;
}
*問い15
格子状の道を縦横に移動した場合何通りの移動方法があるか？
格子が小さいので小学生がやるのと同じ方法で片が付きます。
意外と答えが大きい。
#include<stdio.h>
#include<string.h>
#include<iostream>
int main(){
__int64 memo[21][21];
memset(memo,0,sizeof(memo));
memo[0][0]=1;
for(int i=0;i<21;i++){
for(int j=0;j<21;j++){
if(i>0)memo[i][j]+=memo[i-1][j];
if(j>0)memo[i][j]+=memo[i][j-1];
}
}
std::cout<<memo[20][20];
}
*問い16
２＾1000を１０進数表示した時各桁の和がいくらになるか？
賢い方法を思いつかなかったので簡易多倍張整数型で答える。
計算量が小さいので気にしなかったが添え字の数がとてつもなく大きくなった時のことを考えるとどうなんだろう？
#include<stdio.h>
#include<string.h>
void m(char num[400]){
int a=0;
for(int i=0;i<400;i++){
num[i]=num[i]*2+a;
a=num[i]/10;
num[i]%=10;
}
}
int main(){
char num[400];
memset(num,0,sizeof(num));
num[0]=1;
for(int i=1;i<=1000;i++){
m(num);
}
int sum=0;
for(int i=0;i<400;i++)sum+=num[i];
printf("%d",sum);
}
*問い17
1～1000までの数字を全て英字表記した場合の-とスペースを除いた全文字数を答える問題。
ひたすらめんどくさいだけの問題。
賢い解法とかあるのだろうか？
#include<stdio.h>
#include<map>
#include<string.h>
int main(){
std::map<int,int> memo;
char nums1[][13]={"one","two","three","four","five","six","seven","eight","nine","ten"
,"eleven","twelve","thirteen","fourteen","fifteen","sixteen"
,"seventeen","eighteen","nineteen"};
char nums2[][13]={"twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety","hundred"};
for(int i=1;i<20;i++){
memo[i]=strlen(nums1[i-1]);
}
for(int i=0;i<9;i++){
memo[i*10+20]=strlen(nums2[i]);
}
memo[0]=0;
//printf("%d",memo.size());
int t=0;
for(int i=1;i<100;i++){
if(memo.find(i)==memo.end()){
t+=memo[i/10*10]+memo[i%10];
}else{
t+=memo[i];
}
}
printf("２桁=%d ",t);
int ans=t+11;//1～99までの文字数合計と1000の文字数を足す
for(int i=1;i<10;i++){
int t2=memo[i]+strlen("hundred");//100や200を特別に扱う
ans+=t2;
ans+=(t2+3)*99+t;//1～99までの数字にn hundred andをつけたす
}
printf("%d\n",ans);
}
*問い18
三角形にならんだ数字の中を右下か左下に辿りながら途中のルートの数字の合計が最大になるルートを取った時の最大値を求めよという問題。
動的計画法で楽々。
if文のあたりで少しコードが膨らんでるので?を使って一つの式に纏めればショートコードになるか？
#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int memo[2][20],a,now,next;
sizeof(memo,0,sizeof(memo));
scanf("%d",&memo[0][0]);
for(int i=1;i<15;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;
}
}
//printf("(");
//for(int j=0;j<=i;j++){
//printf("%d,",memo[next][j]);
//}
//printf(")\n");
}
int ans=0;
for(int i=0;i<15;i++)ans=std::max(ans,memo[next][i]);
printf("%d\n",ans);
}
*問い19
20世紀に何回日曜日で始まる月があったかを数える問題。
原理も分からず公式を使って正答。
#include<stdio.h>
int main(){
int j,k,m2,q=1,h,ans=0;
for(int y=1901;y<2001;y++){
for(int m=1;m<13;m++){
if(m<3){
j=(y-1)/100;
k=(y-1)%100;
m2=m+12;
}else{
j=y/100;
k=y%100;
m2=m;
}
h=(q+((m2+1)*26)/10+k+k/4+j/4+5*j)%7;
//printf("(%d %d %d)",y,m,h);
ans+=(h==1);
}
}
printf("%d",ans);
}
*問い20
100！の各桁の和を求める問題。
多倍張整数を実装したりライブラリを探すのがめんどくさかったのでLispで解決。
Lispのコード組み立てるのがかなり苦手、、、
(defun fact (n)
(if (= n 0)
1
(* n (fact (- n 1)))))
fact
(defun sum (n)
(if (= n 0)
0
(+ (mod n 10) (sum (floor n 10)))))
sum
(sum (fact 100))
