「オイラープロジェクト81～90」の編集履歴（バックアップ）一覧はこちら
オイラープロジェクト81～90 - (2012/09/07 (金) 13:18:56) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い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);
}
*問い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());
}
*問い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
縦横高さがそれぞれの辺がｍ以内のボックスがある。
ボックス上の対角にある点まで最短距離で移動するとき移動距離が整数になる場合の数が１００万を超えるサイズｍを求めよという問題。
とりあえずｍ以内の全てのボックスを調べ終えたら、ｍを１大きくした時
最長辺ｍ固定、次に長いｂの辺1～ｍ、３番目に長い辺を１～ｂまでを調べたらサイズが大きくなった時点で追加されたボックスの種類を全部計算できます。
もっと賢い方法がありそうです。
#include<stdio.h>
#include<math.h>
#include<iostream>
int main(){
__int64 m=2,a,b,c,a2,b2,c2,len,s;
int count=0;//m=1は0個
while(count<1000000){
a=m;
a2=a*a;
for(int b=1;b<=m;b++){
for(int c=1;c<=b;c++){
len=(b+c)*(b+c)+a2;
s=sqrt(len);
if(s*s==len){
count++;
}
}
}
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());
}
