「オイラープロジェクト201～210」の編集履歴（バックアップ）一覧に戻る

オイラープロジェクト201～210 - (2012/11/10 (土) 11:47:49) の編集履歴(バックアップ)

---

問い204

ハミング数とは, どの素因数も5以下であるような正整数のことである. 最初から順に並べると, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15となる. 108以下のハミング数は1105個ある.
素因数がn以下の正整数を, type nの一般化ハミング数と呼ぶことにする. するとハミング数はtype 5の一般化ハミング数である.
109以下のtype 100の一般化ハミング数の個数を答えよ.

解法
最初に思いついたコード。
1000万以下の数までハミング数であるかどうかをメモ化していく。
１０００万以上の数は割っていってる最中で、１０００万以下の数になったらその数がハミング数であるかどうかメモ化部分と照合して計算量を下げるコード。
素因数分解の一意性を利用している。
もう少し早く動くかと思ったが答えが出るまで数分かかるので少し遅い、手元のパソコンで３分もかかった。
メモリも結構くってる。
このコードはアプローチの仕方が間違っていた。

#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=100;
const int up2=10000000;
std::vector<int> sosuu;
bool so[up+1];
bool okMemo[up2+1];
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;
sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
	if(so[i]==false)continue;
	sosuu.push_back(i);
	i2=i*2;
	for(int j=i*3;j<up;j+=i2){
		so[j]=false;
	}
}
}
bool isOK(const int n){
int a=n;
bool ans=false,stop=false;
for(int i=0;i<sosuu.size();i++){
	while(a%sosuu[i]==0){
		a/=sosuu[i];
		if(up2>a){
			ans=okMemo[a];
			stop=true;
			break;
		}
	}
	if(stop==true)break;
}
if(up2>n)okMemo[n]=ans;
return ans;
}

int main(){
setSo();
okMemo[1]=okMemo[2]=true;
int ans=2;
for(int i=3;i<=1000000000;i++){
	ans+=isOK(i);
}
printf("%d",ans);
}

より正しいアプローチに変えたコード。
1から掛け算で全ての場合を求めていくコード。
こちらのコードの方が発想がシンプルでコードもすっきりしている。
シンプルですっきりしているということは競技プログラムの大抵の問題でより良いコードが書けたという指標である。
実際こちらは一瞬で答えが出る。

#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=100; 
const int up2=1000000000;
std::vector<int> sosuu;
bool so[up+1];
int ans=0;
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;
sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
	if(so[i]==false)continue;
	sosuu.push_back(i);
	i2=i*2;
	for(int j=i*3;j<up;j+=i2){
		so[j]=false;
	}
}
}

void saiki(int p,__int64 num){
if(num>up2)return;
ans++;
for(int i=p;i<sosuu.size();i++){
	saiki(i,num*sosuu[i]);
}
}
int main(){
setSo();
saiki(0,1);
printf("%d",ans);
}

問い205

ピーターは4面のサイコロを9つ持っている. サイコロの各面には1, 2, 3, 4と書いてある. コリンは6面のサイコロを6つ持っている. サイコロの各面には1, 2, 3, 4, 5, 6と書いてある.
ピーターとコリンはサイコロを投じ, 出た目の合計を比べる. 合計が多い方が勝ちである. もし出た目の合計が等しければ勝負は引き分けになる.
ピーターがコリンに勝つ確率はいくつだろうか? 10進7桁にroundし, 0.abcdefgという形で回答欄に入力せよ.

解法
さいころの数が少ないので動的計画法でさいころの分布を求めて、後はコリンの目がでたらピーターはそれ以上の目を出したばあいの組み合わせを計算して足し合わせていくだけです。
さいころの数が物凄いことになったら標準偏差や数学の知識を駆使しないと解けません。
計算量は大雑把に言って３０００回+memcpy*10回、全探索しても大した量でもないので計算量を抑えた意味はあまりでてません。
プロジェクトオイラーの問題を解いていると自分のレベルの低さがばかり感じます。

#include<stdio.h>
#include<string.h>
int main(){
double memo4[37]={0},memo6[37]={0},next4[37],next6[37];
memo4[0]=memo6[0]=1;
for(int i=0;i<9;i++){
	memset(next4,0,sizeof(next4));
	for(int i=0;i<37;i++){
		for(int j=1;j<5&&i>=j;j++){
			next4[i]+=memo4[i-j];
		}
	}
	memcpy(memo4,next4,sizeof(next4));
}
for(int i=0;i<6;i++){
	memset(next6,0,sizeof(next6));
	for(int i=0;i<37;i++){
		for(int j=1;j<7&&i>=j;j++){
			next6[i]+=memo6[i-j];
		}
	}
	memcpy(memo6,next6,sizeof(next6));
}
double sum4=0,sum6=0,ans=0;
for(int i=0;i<=36;i++){
	sum4+=memo4[36-i];
	memo4[36-i]=sum4;
	sum6+=memo6[i];
}
for(int i=0;i<36;i++){
	ans+=memo4[i+1]*memo6[i];
}
ans=(ans/sum4)/sum6;
printf("%.7lf",ans);
}