「オイラープロジェクト91～100」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト91～100 - (2012/11/21 (水) 13:31:56) のソース
*問い91
ｘｙ平面上の0<=x<=50&&0<=y<=50の範囲で原点と整数座標２点で三角形を作るとき直角三角形はいくつ作ることが出来るか。
計算量の少ない解法を記述するのがめんどくさかったので手抜きでクリア。
全探索しても６２５０万通りと組み合わせ数が少ないので一瞬で計算が終わります。
多分この問題が出題された当時だと１分ルールは切れないのでしょうが今のパソコンでは一瞬ですね。
#include<stdio.h>
#include<algorithm>
int main(){
int a[3];
int size=50,ans=0;
for(int x1=0;x1<=size;x1++){
for(int y1=0;y1<=size;y1++){
if(x1==0&&y1==0)continue;
for(int x2=0;x2<=size;x2++){
for(int y2=0;y2<=size;y2++){
if((x2==0&&y2==0)||(x2==x1&&y2==y1))continue;
a[0]=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
a[1]=x1*x1+y1*y1;
a[2]=x2*x2+y2*y2;
std::sort(a,a+3);
if(a[0]+a[1]==a[2]){
ans++;
}
}
}
}
}
printf("%d",ans/2);
}
*問い92
各桁の２乗を足し合わせた数を求め、それを繰りかすと必ず1か89に到達する。
１０００万以下で89に到達する数の個数を求めよ。
#include<stdio.h>
int memo[1000]={0};
int saiki(int n){
if(n==1||n==89){
return n;
}
if(n<1000&&memo[n]!=0)return memo[n];
int next=0,m=n;
while(m!=0){
next+=(m%10)*(m%10);
m/=10;
}
m=saiki(next);
if(n<1000)memo[n]=m;
return m;
}
int main(){
int ans=0;
for(int i=1;i<10000000;i++){
ans+=(saiki(i)==89);
}
printf("%d",ans);
}
*問い94
一辺の長さが整数の正三角形は面積が整数にならないことを示すのは簡単である. しかし, 5-5-6の辺を持つ殆ど正三角形に近い擬正三角形 (almost equilateral triangle) は面積が12で整数である.
以降, 二等辺三角形で, 3つめの辺の長さが他と1つしか違わないもの (5-5-6, 5-5-4等) を, 擬正三角形と呼ぶ.
さて, 周囲の長さが1,000,000,000以下の面積が整数になる擬正三角形を考え, その周囲の長さの総和を求めよ.
解法
低速な解法を見つけました。
コード実行時間 97.41秒。
三辺の長さを(a,a,a+1)とあらわしたときヘロンの公式より
s=(3a+1)/2
S^2=1/16*(3s+1)(s+1)(s+1)(s-1)の４つの項を個別に素因数分解して素因数の個数を足し合わせます。、
素因数が２を4つ以上含みかつ全ての素因数の個数が全て偶数であるならその面積Sは自然数になることを利用します。
ここで
(3s+1)
(s+1)
(s+1)
(s-1)
を個別に検証します。
素因数分解したら２が何個で３が何個でと数えてきます。
(s+1)(s+1)の素因数はどの数も個数が２の倍数となるので、これは1/16を打ち消すために２が何個含まれているかだけを数えます。
次に(3s+1)(s-1)に何個素因数が含まれているかですが、g=gcd((3s+1),s-1)を取るとgは3s+1とs-1から素因数をとってくるのでｇは必ずどの素因数も個数が２の倍数となります。
よってｇは1/16を打ち消すために２の個数だけを数え、残りはｇを除外した(3s+1)/gと(s-1)/gの素因数でどの数も偶数個ずつ含まれているかだけをチェックすればいいことが判明します。
２つずつでないと意味がないので割る数は必ず素数の２乗をチェックすることで計算量を抑えます。
(a,a,a-1)も同様の考え方をします。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<set>
#include<time.h>
const int up=34000;
std::vector<int> sosuu2;
std::set<int> memo;
bool so[up+1];
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
memo.insert(1);
sosuu2.push_back(4);
memo.insert(4);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu2.push_back(i*i);
memo.insert(i*i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
bool check(int a,int& count2){
while(a>0&&a%2==0){
a/=2;
count2++;
}
for(int i=0;sosuu2[i]*sosuu2[i]<=a;i++){
int p=sosuu2[i];
while(a%p==0){
a/=p;
}
}
return memo.find(a)!=memo.end();
}
bool calc(const int n,const int add){
int a=n+add;
int count2=-4;
while(a>0&&a%2==0){
a/=2;
count2+=2;
}
int g=gcd(3*n+add,n-add);
a=g;
while(a>0&&a%2==0){
a/=2;
count2+=2;
}
a=(3*n+add)/g;
if(check(a,count2)==false)return false;
a=(n-add)/g;
if(check(a,count2)==false)return false;
if(count2<0||count2%2==1)return false;
return true;
}
int main(){
double start=clock();
setSo();
int limit=10000*10000*10;
__int64 ans=0;
for(int n=3;3*n+1<=limit;n+=2){
ans+=calc(n,1)*(3*n+1);
}
for(int n=3;3*n-1<=limit;n+=2){
ans+=calc(n,-1)*(3*n-1);
}
std::cout<<"\nans="<<ans<<" time="<<clock()-start;
}
Yahoo知恵袋でのアドバイスをもとにコードを改善して実行時間１１秒まで短縮。
下記コードはBCC5.5ではSQRT関数の精度の関係で上手く動かずGCCではきちんと動く。
最初BCCで実装したために上記コードのような回りくどい方法をとってましたが、下記コードはGCCではきちんと動きます。
内部的なアルゴリズムが違うようだ。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<set>
#include<time.h>
#include<math.h>
const int up=34000;
std::vector<int> sosuu2;
std::set<int> memo;
bool so[up+1];
bool calc(long long int n){
long long int s=sqrt(n);
return s*s==n;
}
int main(){
double start=clock();
int limit=10000*10000*10;
long long int ans=0;
for(long long int n=3;3*n+1<=limit;n+=2){
if(calc((3*n+1)*(n-1))){
std::cout<<n<<" "<<n<<" "<<n+1<<"\n";
ans+=3*n+1;
}
}
std::cout<<"\n";
for(long long int n=3;3*n-1<=limit;n+=2){
if(calc((3*n-1)*(n+1))){
std::cout<<n<<" "<<n<<" "<<n-1<<"\n";
ans+=3*n-1;
}
}
std::cout<<"\nans="<<ans<<" time="<<clock()-start;
}
*問い95
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095
100万以下の要素で構成された友愛鎖のうち一番長い鎖の一番小さい値を求めよ。
メモ化で高速化のつもりが妙に時間がかかった。
もう少し早いつもりだったんだけどな。
#include<stdio.h>
#include<math.h>
#include<iostream>
const int up=1000000;
int memo[up+2]={0};
__int64 wa(int n){
__int64 up=sqrt(n),c1,t,re=1,s=n;
for(int i=2;i<=up;i++){
c1=1;
t=1;
while(n%i==0){
n/=i;
t*=i;
c1+=t;
}
re*=c1;
}
if(n!=1){
re*=(n+1);
}
return re-s;
}
int saiki(__int64 n,int s,int deep){
if(n>=up)return 0;//100万を超えてしまった
if(s==n&&deep>0)return deep;//輪になった
if(memo[(int)n]!=0)return 0;//他の輪に外から入ってしまった
memo[(int)n]=1;//とりあえず使用済みにしておく
int re=saiki(wa(n),s,deep+1);
memo[(int)n]=re;//正式にループの長さが決まった
return re;
}
int main(){
for(int i=2;i<up;i++){
if(memo[i]==0){
saiki(i,i,0);
}
}
int ans,loopSize=0;
for(int i=0;i<up;i++){
if(memo[i]>loopSize){
ans=i;
loopSize=memo[i];
}
}
printf("%d %d\n",ans,loopSize);
}
*問い97
28433×2^7830457+1は素数でありこれの下１０ケタを答えよという問題。
Ｌｉｓｐは苦手だけどＬｉｓｐでなかったらこんなに簡潔には書けない気もする。
Ｌｉｓｐ様様って感じ（俺がヘボいだけかな）
(defvar mask 10000000000)
mask
(setq mask 10000000000)
10000000000
(defun saiki (n m all)
(if (< 0 m)
(if (= (mod m 2) 1)
(saiki (mod (* n n) mask) (floor (/ m 2)) (mod (* all n) mask))
(saiki (mod (* n n) mask) (floor (/ m 2)) all))
all))
saiki
(mod (+ (* (saiki 2 7830457 1) 28433) 1) mask)
*問い98
CARE という単語の各文字をそれぞれ 1, 2, 9, 6 に置き換えることによって, 平方数 1296 = 362 ができる. 注目すべきことに, 同じ数字の置換をつかうことにより, アナグラムの RACE も平方数 9216 = 962 をつくる. CARE (と RACE) を平方アナグラム単語対と呼ぼう. 先頭のゼロは許されず, 異なる文字が同じ数字をもつこともないとする.
約 2,000 個の一般的な英単語を含む 16K のテキストファイルwords.txt (右クリックして "名前をつけてリンク先を保存") を用いて, 平方アナグラム単語対をすべて求めよ (回文となる単語はそれ自身のアナグラムとはみなさない).
そのような対のメンバーから作られる最大の平方数は何か?
注: 作られるアナグラムは, すべて与えられたテキストファイルに含まれている
ひたすらめんどくさいだけの問題。
面倒だったので邪道なテクニックを使ってアセプト。
文字列をなるたけ手前から直接数字列に変換して(￥0を避けるために、+1大きく変換)して最後に数字に直して平方数かチェック。
これを再帰関数を使って実装した。
それでもコードサイズが膨らんだ、、、
この問題の正答率が低いのはとにかくめんどくさいからに違いない。
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<map>
#include<string>
#include<vector>
#include<iostream>
//何だかめんどくさい問題なので邪道な手口を使ってコードを短縮する
//実務では100％禁じ手だろうな
struct S{
int cs[27];
bool operator<(const S& s)const{
for(int i=0;i<27;i++){
if(cs[i]!=s.cs[i])return cs[i]<s.cs[i];
}
return false;
}
};
__int64 ans=0;
int spents[11]={0};
__int64 stringToNum(std::string str){
if(str[0]==1)return -1;//小さい数字なら何でもいい
__int64 re=0;
for(int i=0;str[i]!='\0';i++){
re=re*10+(str[i]-1);
}
return re;
}
void saiki(int deep,std::string w1,std::string w2){
if(deep==w1.size()){
__int64 k1,k2,n1=stringToNum(w1),n2=stringToNum(w2);
if(n1==1||n2==1)return;
k1=sqrt(n1);
k2=sqrt(n2);
if(k1*k1==n1&&k2*k2==n2){
if(ans<n1)ans=n1;
if(ans<n2)ans=n2;
//std::cout<<"("<<n1<<" "<<n2<<")";
}
}else{
//この文字は数字に変換済み
if(w1[deep]<11){
saiki(deep+1,w1,w2);
return ;
}
__int64 next1,next2;
std::string nextW1,nextW2;
char c;
for(int i=1;i<11;i++){
//\0の取り扱いがめんどくさいので数字を1大きくして文字列を数字に変換する
//実務でないからこそだな
if(i==1&&deep==0)continue;
if(spents[i]==0){
spents[i]=1;
nextW1=w1;
nextW2=w2;
c=w1[deep];
for(int j=0;j<w1[j]!='\0';j++){
if(w1[j]==c){
nextW1[j]=i;
}
if(w2[j]==c){
nextW2[j]=i;
}
}
saiki(deep+1,nextW1,nextW2);
spents[i]=0;
}
}
}
}
int main(){
char front[10],text[20],c;
FILE *fp;
if ((fp = fopen("euler98Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
S s;
std::vector<std::string> vec;
std::map<S,std::vector<std::string> > memo;
std::map<S,std::vector<std::string> >::iterator it;
std::string str1,str2;
while(fscanf(fp,"%[^\"]\"%[^\"]\"",front,text)!=EOF){
memset(s.cs,0,sizeof(s.cs));
for(int i=0;text[i]!='\0';i++){
s.cs[text[i]-'A']++;
}
if(memo.find(s)==memo.end()){
vec.push_back(text);
memo[s]=vec;
vec.pop_back();
}else{
memo[s].push_back(text);
}
if(fscanf(fp,"%c",&c)==EOF)break;
}
fclose(fp);
printf("\nallRead\n");
for(it=memo.begin();it!=memo.end();it++){
//テキストを解析した結果対になるアナグラムが３つ以上はないことが判明
if((*it).second.size()>1){
str1=(*it).second[0];
str2=(*it).second[1];
std::cout<<"<"<<str1<<" "<<str2<<">\n";
saiki(0,str1,str2);
}
}
std::cout<<ans<<"\n";
}
*問い99
数万＾数万乗形式の大きな数が1000行与えられるので一番大きな数字の書かれた行を探せという問題。
対数を使って計算すれば楽勝。
楽勝なんだけど、このコードで合格出来たけど一応1だけ数字が違うのきたら大小関係が判別できないはずだけどこれで合格でいいのかな？
#include<stdio.h>
#include<math.h>
int main(){
double a,b,c,myMax=0;
int ansNo;
for(int i=0;i<1000;i++){
scanf("%lf,%lf",&a,&b);
c=log(a)*b;
printf("( %lf %lf)\n",log(a),b);
if(c>myMax){
myMax=c;
ansNo=i+1;
}
}
printf("%d\n",ansNo);
}
＊問い100
箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて、無作為に2つ取り出すとき、青い円盤2つを取り出す確率P(BB)は
P(BB) = (15/21) × (14/20) = 1/2
であることがわかる。
無作為に2つ取り出すとき、青い円盤2つを取り出す確率がちょうど1/2となるような次の組み合わせは、箱が85個の青い円盤と35個の赤い円盤からなるときである。
箱の中の円盤の合計が1012 = 1,000,000,000,000を超えるような最初の組み合わせを考える。箱の中の青い円盤の数を求めよ
値が小さな場合について全探索で求め、出てきた数列を眺めた結果。
(A/N)*(A-1)/(N-1)=1/2に
C(i+1)=(Ni+Ai)-1
N(i+1)-A(i+1)=C(i+1)という関係を見つけたので後は式変形したら２次方程式を介した漸化式となりました。
とりあえず見つけただけでCiが何故成立するか分かってません。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include <iomanip>
int main(){
double a=15,n=21,n2,a2,c;
std::cout.precision(4);
std::cout.setf(std::ios::fixed);
while(n<1000000000000.0){
c=a+n-1;
n2=(1+4*c+sqrt(8*c*c+1))/2.0;
a=n2-c;
n=n2;
std::cout<<a<<"/"<<n<<"\n";
}
}
