「プロジェクトオイラー問い101～110」の編集履歴（バックアップ）一覧に戻る
*問い102 内部に原点を含む三角形はファイル内にいくつあるでしょう?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20102
3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.
以下の2つの三角形を考える.
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.
27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.
注: ファイル中の最初の二つは三角形ABC, XYZである.
解法
3つの点のうち2点を選ぶ組み合わせ3通りで外積の正負が3通りとも同じならその三角形は原点を内部に含みます。
#include<stdio.h>
int main(){
int xs[3],ys[3];
char c1,c2;
int ans=0;
for(int i=0;i<1000;i++){
for(int i=0;i<3;i++)scanf("%d%c%d%c",&xs[i],&c1,&ys[i],&c2);
int p=0,m=0;
for(int i=0;i<3;i++)xs[i]*ys[(i+1)%3]-ys[i]*xs[(i+1)%3]>=0?p++:m++;
if(p==3||m==3)ans++;
}
printf("%d",ans);
}
*Problem 104 「先頭9桁と末尾9桁が1から9までの数字をすべて含むフィボナッチ数を求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20104
解法
この問題は多分上位十数ケタと下位9ケタまでを保存しておいて、別々に計算すれば良いだろうなと思いつつ、一応真面目に全桁計算でチャレンジしてみたらいつまでたっても計算が終わらなかったorz
しょうがないので検索かけてカンニングしてみたら大体同じ考え方で解けるみたい。
まじめにやるとあの高速なＬｉｓｐの処理系で時間がかかるとは恐るべき問題。
繰上りで伝播していく時、桁の増加スピードの方が繰上りの伝播スピードより大きくなる桁数が3桁か4桁あたりにあるんだろうな。
一つ勉強になった。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
__int64 maskDown=1,maskUp=1;
int check(__int64 num){
char str[11];
while(num>=maskDown)num/=10;
sprintf(str,"%d",num);
int count[10]={1,0,0,0,0,0,0,0,0,0};
for(int i=0;i<9;i++){
count[str[i]-'0']++;
if(count[str[i]-'0']>1)return false;
}
return true;
}
int main(){
__int64 upF1=1,upF2=1,downF1=1,downF2=1,upF3,downF3;
for(int i=0;i<9;i++)maskDown*=10;
for(int i=0;i<17;i++)maskUp*=10;
int ans=2;
printf("");
while(check(upF2)==false||check(downF2)==false){
upF3=upF1+upF2;
upF1=upF2;
upF2=upF3;
downF3=downF1+downF2;
downF1=downF2;
downF2=downF3;
while(maskUp<upF2&&maskUp<upF1){
upF2/=10;
upF1/=10;
}
downF2%=maskDown;
ans++;
}
std::cout<<upF2;
printf(" %d",ans);
}
*Problem 105 「ファイル内の特殊和集合の和を求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20105
与えられたデータが特殊和集合かどうかをチェックする問題。
解法
最大でも12個と少ないので3＾12個を全探索しても大した計算量ではありません。
なので全探索します。
#include<stdio.h>
int data[12];
bool saiki(int sum1,int sum2,int count1,int count2,int deep,int last){
if(sum1==sum2&&count1>0&&count2>0)return false;
if(sum1>=sum2&&count1<count2)return false;
if(sum1<=sum2&&count1>count2)return false;
bool re=true;
if(deep==last){
return true;
}else{
re=re&&saiki(sum1+data[deep],sum2,count1+1,count2,deep+1,last);
if(re==false)return re;
re=re&&saiki(sum1,sum2+data[deep],count1,count2+1,deep+1,last);
if(re==false)return re;
re=re&&saiki(sum1,sum2,count1,count2,deep+1,last);
if(re==false)return re;
}
return re;
}
int main(){
int ans=0;
char c;
for(int i=0;i<100;i++){
int last=0;
int sum=0;
while(1){
scanf("%d%c",&data[last],&c);
sum+=data[last];
last++;
if(c=='\n')break;
}
ans+=saiki(0,0,0,0,0,last)*sum;
}
printf("%d",ans);
}
*Problem 107 「ネットワークを連結する最も効率的な方法を特定せよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20107
ネットワークを最小コストで繋げる問題。
解法
プリムで一発です。
プリムについて知らなかったとき自分で全く同じものを編み出した経験があるので何も見なくても簡単に書けます。
#include<stdio.h>
#include<queue>
#include<stdlib.h>
int G[41][41];
int cons[41]={0};
int all=0;
struct S{
int no,cost;
bool operator<(const S& s)const{
return cost>s.cost;
}
};
void calc(){
int count=0;
S s,nextS;
s.cost=s.no=0;
std::priority_queue<S> qu;
qu.push(s);
while(!qu.empty()){
s=qu.top();
qu.pop();
if(cons[s.no]!=0)continue;
printf("(%d %d)",s.no,s.cost);
cons[s.no]=1;
all-=s.cost;
count++;
if(count==40)break;
for(int i=0;i<40;i++){
if(G[s.no][i]==-1||cons[i]==1)continue;
nextS.no=i;
nextS.cost=G[s.no][i];
qu.push(nextS);
}
}
printf("%d",all);
}
void setData(){
char text[10],c;
int num;
for(int i=0;i<40;i++){
for(int j=0;j<40;j++){
scanf("%[0123456789-]%c",text,&c);
if(text[0]=='-'){
G[i][j]=-1;
}else{
sscanf(text,"%d",&num);
G[i][j]=num;
all+=num;
}
}
}
all/=2;
}
int main(){
setData();
calc();
}
*Problem 108 「ディオファントス方程式 1/x + 1/y = 1/n を解け」 †
次の等式で x,y,n は正の整数である.
1/x + 1/y = 1/n
n = 4 では 3 つの異なる解がある.
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4
解の数が 1000 を超える最小の n を求めよ.
解法
1/x+1/y=1/nを式変形すると
n^2=(x-n)(y-n)となります。
ｘとｙは独立な自然数なのでこの条件を満たす数(x-n)と(y-n)の組を調べます。
組み合わせについてはn>=(x-n)となる範囲を調べれば十分です。
#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
int ans;
std::map<__int64,int> memo;
void saiki(__int64 n,__int64 limit,std::map<__int64,int>::iterator it,int count){
if(n>limit)return;
ans++;
int add=1;
while(it!=memo.end()){
if(count<(*it).second)saiki(n*(*it).first,limit,it,count+add);
add=0;
count=1;
it++;
}
}
void calc(__int64 num){
__int64 limit=num;
memo.clear();
ans=0;
for(__int64 i=2;i*i<=num;i+=(i&1)+1){
int count=0;
while(num%i==0){
num/=i;
count++;
}
if(count>0)memo[i]=count*2;
}
if(num!=1){
if(memo.find(num)==memo.end())memo[num]=0;
memo[num]+=2;
}
saiki(1,limit,memo.begin(),0);
}
int main(){
__int64 n=2;
while(1){
calc(n);
if(ans>1000)break;
n++;
}
std::cout<<n;
}
*Problem 109 「ダーツゲームでプレーヤーが100点未満でチェックアウトできる異なる方法は何通りあるか?」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20109
ダーツの得点の組み合わせを求める問題。
全部の場合を検証しても計算量はたいしたことありません。
よって３重ループで片が付きます。
#include<stdio.h>
#include<vector>
int main(){
std::vector<int> ps;
ps.push_back(0);
for(int i=1;i<=20;i++)ps.push_back(i);
ps.push_back(25);
for(int i=1;i<=20;i++)ps.push_back(i*2);
ps.push_back(50);
for(int i=1;i<=20;i++)ps.push_back(i*3);
int ans=0;
for(int i=0;i<ps.size();i++){
for(int j=i;j<ps.size();j++){
for(int k=22;k<=42;k++){
if(ps[i]+ps[j]+ps[k]<100)ans++;
}
}
}
printf("%d",ans);
}
*Problem 110 「方程式 1/x + 1/y = 1/n の解の個数を解析する効率的なアルゴリズムを求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20110
次の等式で x,y,n は正の整数である.
1/x + 1/y = 1/n
n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.
解の数が 4,000,000 を超える最小の n を求めよ.
注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.
解法
この問題は苦労した、解を自力で思いつくまで3日もかかったから。
1/x+1/y=1/nを式変形すると
n^2=(x-n)(y-n)
ここでｎを指定しn^2因数分解したものを(x-n)と(y-n)に分配したくなるのが人情である。
ここで視点を変えて、(x-n)と(y-n)を因数の掛け算としてボトムアップで生成すれば良い。
答えは16桁、ｎを一つ一つ検査していてはどんなに早いコードでも終わらないサイズ。
前から駄目なら後ろから、縦のものを横にするだけの簡単な発想、気づくか気づかないかの問題というのが感想。
#include<stdio.h>
#include<iostream>
__int64 ps[]={2,3,5,7,11,13,17,19,23,29,31,37,39,41,43};
__int64 ans=0;
void saiki(unsigned __int64 num,unsigned __int64 perm,int limit,int p){
if(perm+1>=8000*1000){
if(ans==0||ans>num)ans=num;
return ;
}
if(ans!=0&&num>=ans)return;
__int64 a,b;
a=ps[p];
b=1;
for(;b<=limit;b++){
saiki(a*num,perm*(2*b+1),b,p+1);
if(ans!=0&&a*num>=ans)break;
if(perm*(2*b+1)+1>=8000*1000)break;
a*=ps[p];
}
}
int main(){
saiki(1,1,1999999,0);
std::cout<<ans;
}
