オイラープロジェクト81～90

問い81

http://projecteuler.net/problem=81
正方行列の左上からスタートし右か下に移動しながら右下まで到達するときルートの総計が最小になるルートを取った時の値を答えよ。
動的計画法で瞬殺。

#include<stdio.h>
#include<algorithm>
int main(){
int a,memo[82][82];
memset(memo,0,sizeof(memo));
for(int i=1;i<81;i++){
	for(int j=1;j<81;j++){
		if(j==80)scanf("%d",&a);
		else scanf("%d,",&a);
		if(i==1)memo[i][j]=memo[i][j-1]+a;
		if(j==1)memo[i][j]=memo[i-1][j]+a;
		if(i!=1&&j!=1)memo[i][j]=std::min(memo[i-1][j],memo[i][j-1])+a;
	}
	printf("<%d>",i);
}
printf("%d",memo[80][80]);
}

問い82

問い81のスタート地点が左端、ゴールが右端になった問題。
特殊なグラフとして見て、ダイクストラ法で一発。

#include<stdio.h>
#include<queue>
struct S{
int x,y,sum;
bool operator<(const S& s)const{
	return sum>s.sum;
}
};
int main(){
int map[81][81];
int cost[81][81];
for(int i=0;i<80;i++){
	for(int j=0;j<79;j++){
		scanf("%d,",&map[i][j]);
		cost[i][j]=1000000000;
	}
	scanf("%d",&map[i][79]);
	cost[i][79]=1000000000;
}
printf("allRead");
S s,next;
s.x=0;
std::priority_queue<S> pQ;
for(int r=0;r<80;r++){
	s.y=r;
	s.sum=map[r][0];
	pQ.push(s);
}
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
while(pQ.empty()==false){
	s=pQ.top();
	if(s.x==79)break;
	pQ.pop();
	if(cost[s.y][s.x]<s.sum)continue;
	for(int i=0;i<4;i++){
		next.x=s.x+dxs[i];
		next.y=s.y+dys[i];
		if(next.x<0||79<next.x||next.y<0||79<next.y)continue;
		next.sum=s.sum+map[next.y][next.x];
		if(next.sum>=cost[next.y][next.x])continue;
		cost[next.y][next.x]=next.sum;
		pQ.push(next);
	}
}
printf("<%d>",s.sum);
}

問い83

問い81のスタートとゴールが同じで上下左右に移動してよいという問題。
これは82をちょっと変えるだけで瞬殺。

#include<stdio.h>
#include<queue>
struct S{
int x,y,sum;
bool operator<(const S& s)const{
	return sum>s.sum;
}
};
int main(){
int map[81][81];
int cost[81][81];
for(int i=0;i<80;i++){
	for(int j=0;j<79;j++){
		scanf("%d,",&map[i][j]);
		cost[i][j]=1000000000;
	}
	scanf("%d",&map[i][79]);
	cost[i][79]=1000000000;
}
printf("allRead");
S s,next;
s.x=0;
s.y=0;
s.sum=map[0][0];
std::priority_queue<S> pQ;
pQ.push(s);
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
while(pQ.empty()==false){
	s=pQ.top();
	if(s.x==79&&s.y==79)break;
	pQ.pop();
	if(cost[s.y][s.x]<s.sum)continue;
	for(int i=0;i<4;i++){
		next.x=s.x+dxs[i];
		next.y=s.y+dys[i];
		if(next.x<0||79<next.x||next.y<0||79<next.y)continue;
		next.sum=s.sum+map[next.y][next.x];
		if(next.sum>=cost[next.y][next.x])continue;
		cost[next.y][next.x]=next.sum;
		pQ.push(next);
	}
}
printf("<%d>",s.sum);
}

問い85

注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.
ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 一番近い解を持つような格子の面積を求めよ.

縦a,横bとするとa*(a+1)/2*b*(b+1)/2個の長方形が含まれているので後は縦を一つずつ試しながら一番小さくなるｂをstd::mapから求めていくだけです。

#include<stdio.h>
#include<map>
#include<math.h>
int main(){
std::map<int,int> memo;
std::map<int,int>::iterator it;
int mymax=200*10000;//200万
int sum=1,up=sqrt(mymax),i;
memo[0]=0;
//縦a,横ｂとして200万≒a(a+1)/2*b(b+1)/2
for(i=2;sum<=mymax;){
	memo[sum]=i-1;
	sum+=i;
	i++;
}
memo[sum]=i-1;
int b,sa=200*10000,h,w,c;
sum=1;	
for(int a=2;sum<=up;a++){
	b=mymax/sum;
	it=memo.upper_bound(b);
	c=sum*(*it).first;
	if(abs(c-mymax)<sa){
		sa=abs(c-mymax);
		h=a-1;
		w=(*it).second;
	}
	it--;
	c=sum*(*it).first;
	if(abs(c-mymax)<sa){
		sa=abs(c-mymax);
		h=a-1;
		w=(*it).second;
	}
	sum+=a;
}
printf("%d %d,%d %d\n",w,h,w*h,sa);
}

問い86

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2086
縦横高さがそれぞれの辺がｍ以内のボックスがある。
ボックス上の対角にある点まで最短距離で移動するとき移動距離が整数になる場合の数が１００万を超えるサイズｍを求めよという問題。

とりあえずｍ以内の全てのボックスを調べ終えたら、次にｍを１大きくした時
最長辺aをｍに固定、次に長い辺をｂとしこれを1～ｍ、３番目に長い辺cを１～ｂまでとしこれを全て調べたらｍが1大きくなった時の全ての追加パタンを調べたことになります。
ここで最短辺は(b+c)^2+a^2でもとまりますがb+cが同じ長さになるものをまとめて計算して計算量を落とします。
これでｍが1拡張された時に追加されるボックスだけを計算できます。

#include<stdio.h>
#include<math.h>
#include<iostream>
int main(){
__int64 m=1,a,len,a2,s,c;
int count=0,add;//m=1は0個
while(count<1000000){
	a=m;
	a2=a*a;
	add=1;
	for(int d=0;d<m;d++){
		c=d+2;
		len=c*c+a2;
		s=sqrt(len);
		if(s*s==len){
			count+=add;
		}
		if(d==m-1)break;
		c=2*m-d;
		len=c*c+a2;
		s=sqrt(len);
		if(s*s==len){
			count+=add;
		}
		add+=d&1;
	}
	m++;
}
std::cout<<m-1<<" "<<count;
}

問い87

5000万>素数^2+素数^3+素数^4と表現できる数字の個数を答えよ。
読解ミスしてかなり間違えた問題。
5000万未満の数字が何個あるかというところを何通りの式で表すことが出来るかと読解ミスして間違えた。
恥ずかしい。。。

#include<stdio.h>
#include<math.h>
#include<vector>
#include<set>

const int up=50000000;
std::vector<int> sosuu;

bool so[7100];//50000000の大雑把な平方根

void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	sosuu.push_back(2);
	for(int i=3;i<=sqrt(up);i+=2){
		if(so[i]==false)continue;
		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<sqrt(up);j+=i2){
			so[j]=false;
		}
	}
}
int main(){
	setSo();
	//for(int i=0;i<sosuu.size();i++){
		//printf("%d ",sosuu[i]);
	//}
	int t=8,p;
	std::vector<int> p2,p3,p4;
	for(int i=1;t<up;i++){
		p3.push_back(t);
		p=sosuu[i];
		t=p*p*p;
	}
	t=16;
	for(int i=1;t<up;i++){
		p4.push_back(t);
		p=sosuu[i];
		t=p*p*p*p;
	}
	for(int i=0;i<sosuu.size();i++){
		p2.push_back(sosuu[i]*sosuu[i]);
	}
	for(int i=0;i<p2.size();i++){
		//printf("%d ",p2[i]);
	}
	
	
	std::set<int> ans;
	for(int i=0;i<p4.size();i++){
		for(int j=0;j<p3.size();j++){
			t=up-(p4[i]+p3[j])-1;
			for(int k=0;p2[k]<=t&&k<p2.size();k++){
				ans.insert(p4[i]+p3[j]+p2[k]);
			}
		}
	}
	printf("%d",ans.size());
}

問い88

少なくとも2つの自然数 {a1, a2, ... , ak} の集合の和かつ積として表せる自然数Nを積和数と呼ぶ：N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.
例えば, 6 = 1 + 2 + 3 = 1 × 2 × 3.
ある集合の大きさ k に対して,この性質を持つ最小の N を最小積和数と呼ぼう. 集合の大きさ k = 2, 3, 4, 5, 6 に対する最小積和数は次のとおりである.
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
したがって 2≦k≦6 に対して,全ての最小積和数の和は 4+6+8+12 = 30 である. 8 は和に一度だけカウントされていることに気をつけよう.
実際、2≦k≦12 に対する最小積和数の完全な集合は {4, 6, 8, 12, 15, 16} なので,その和は 61 である.
2≦k≦12000 に対する全ての最小積和数の和は何か?

解法

枝刈付きの幅優先探索でもまあそれなりの速度は出たのでこれで満足しました。
一瞬で答えを出せるような高速化する方法もありそうな問題なので後日リベンジするかもしれません。

何か考えミスがあって桁あふれしても困るので、とりあえずできる限り__int64を使うのが私の習慣です。

#include<stdio.h>
#include<queue>
#include<string.h>
#include<set>
#include<iostream>
struct S{
__int64 wa,mul,d;
int p;
};
__int64 ans[12001];
const int last=12000;
void calc(int p){
__int64 wa=p,n1=2,n2;
std::queue<S> qu;
S s1,s2;
while(1){
	n2=n1;
	while(1){
		if(wa+n1+n2<n1*n2)break;
		s1.wa=wa+n1+n2;
		s1.mul=n1*n2;
		s1.d=n2;
		s1.p=p+2;
		qu.push(s1);
		n2++;
	}
	if(n1==n2)break;
	n1++;
}
while(!qu.empty()){
	s1=qu.front();
	qu.pop();
	if(s1.p>last)break;
	n1=ans[s1.p];
	if(s1.wa==s1.mul){
		if(n1==-1||n1>s1.wa)ans[s1.p]=s1.wa;
		continue;
	}		
	n1=s1.d;
	while(1){
		s2.wa =s1.wa+n1;
		s2.mul=s1.mul*n1;
		s2.d=n1;
		s2.p=s1.p+1;
		if(s2.wa<s2.mul)break;
		qu.push(s2);
		n1++;
	}
}
}
int main(){
memset(ans,-1,sizeof(ans));
for(int i=0;i<last-1;i++){
	calc(i);
	std::cout<<i<<"\n";
}
std::set<__int64> memo;
std::set<__int64>::iterator it;
for(int i=2;i<=last;i++){
	memo.insert(ans[i]);
}
__int64 sum=0;
for(it=memo.begin();it!=memo.end();it++){
	sum+=(*it);
}
std::cout<<sum;
}

問い89

ローマ数字が１０００個与えられるので、数字を最短の長さに書き直したとき何文字節約できるか求めよという問題。
ローマ数字は後ろから読んでいくと綺麗に１０進数になおすことができます。
後は各桁バラバラに最短を求めるだけです。

#include<stdio.h>
#include<string.h>
int toOneNum(char c){
int re;
if(c=='I')re=1;
if(c=='V')re=5;
if(c=='X')re=10;
if(c=='L')re=50;
if(c=='C')re=100;
if(c=='D')re=500;
if(c=='M')re=1000;
return re;
}
int toNum(char text[50]){
int num,now,back=toOneNum(text[strlen(text)-1]);
num=back;
for(int i=strlen(text)-2;i>=0;i--){
	now=toOneNum(text[i]);
	if(now<back){
		num-=now;
	}else{
		num+=now;
	}
	back=now;
}
return num;
}
int oneMin(int n){
if(n<3)return n;
if(n==4||n==6||n==9)return 2;
//残りは3　5　7　8
if(n==5)return 1;
if(n==3||n==7)return 3;
if(n==8)return 4;
return -1000;//これはあり得ない
}
int main(){
int num,ans=0;
char text[50];
for(int i=0;i<1000;i++){
	scanf("%s",text);
	num=toNum(text);
	//printf("(%d %d)",strlen(text),num);
	int len=num/1000;//まずは1000以上を並べる
	num%=1000;
	len+=oneMin(num%10);//1桁目
	num/=10;
	len+=oneMin(num%10);//２桁目
	num/=10;
	len+=oneMin(num%10);//３桁目
	//printf("%d %d %d\n",strlen(text),len,strlen(text)-len);
	ans+=strlen(text)-len;
}
printf("%d",ans);
}

タグ：

+ タグ編集

「オイラープロジェクト81～90」をウィキ内検索

最終更新：2012年10月03日 12:46

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス