「オイラープロジェクト151～160」の編集履歴（バックアップ）一覧はこちら

「オイラープロジェクト151～160」(2012/11/24 (土) 13:15:24) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い151
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20151
封筒の中身の期待値を求める問題。


シンプルに動的計画法で期待値を求めるだけです。
丁寧ですがコードサイズが膨らみました。
この問題簡単すぎますが他の人のコードを読んでると楽しい問題です。
問題をどんな構造で解くか。
色々なとらえ方があって楽しいですね。




 #include<stdio.h>
 #include<map>
 #include<string.h>
 #include<iostream>
 #include<time.h>
 struct E{
	__int64 paper[6];
	bool operator<(const E& e)const{
		for(int i=1;i<=5;i++){
			if(paper[i]!=e.paper[i])return paper[i]<e.paper[i];
		}
		return false;
	}
	void print(){
		std::cout<<"(";
		for(int i=1;i<=5;i++){
			std::cout<<paper[i]<<" ";
		}
		std::cout<<")";
	}
 };
 int main(){
	double start=clock();
	double ans=0,perm,p;
	std::map<E,double> memo,next;
	std::map<E,double>::iterator it;
	E e,es[6];
	memset(e.paper,0,sizeof(e.paper));
	for(int i=1;i<=5;i++){
		es[i]=e;
		es[i].paper[i]=1;
	}
	e.paper[1]=1;
	memo[e]=1.0;	
	for(int i=1;i<=14;i++){
		for(it=memo.begin();it!=memo.end();it++){
			double paperCount=0;
			e=(*it).first;
			for(int j=1;j<=5;j++){
				paperCount+=e.paper[j];
			}
			if(paperCount==0)continue;
			for(int j=1;j<=5;j++){
				e=(*it).first;
				if(e.paper[j]<1)continue;
				e.paper[j]--;
				for(int k=j+1;k<=5;k++){
					e.paper[k]++;
				}
				if(next.find(e)==next.end())next[e]=0;
				next[e]+=(*it).second*(e.paper[j]+1.0)/paperCount;
			}
		}
		memo.clear();
		memo.insert(next.begin(),next.end());
		next.clear();
		for(int i=1;i<=5;i++){
			ans+=memo[es[i]];
		}
		std::cout<<i+1<<" "<<ans<<" "<<memo.size()<<"\n";
	}
	std::cout<<"ans="<<ans<<" time="<<clock()-start;
 }


他の人のコードを参考にショートコードを作ってみました。
私はショートコードに向いてないなと痛感した次第です。

 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 double memo[2][131072]={{0,1.0,0},{0}};
 int main(){
	double ans=0,all;
	int slide[]={0,1,3,6,11},mask[]={1,3,7,31,63},add[]={2121,2118,2104,1984,-2048};
	for(int i=1;i<=14;i++){
		int now=(i+1)&1,next=i&1;
		memset(memo[next],0,sizeof(memo[next]));
		for(int j=0;j<131072;j++){
			all=0;
			for(int size=0;size<5;size++)all+=(j>>slide[size])&mask[size];
			for(int size=0;size<5;size++){
				if(((j>>slide[size])&mask[size])!=0){
					int p=j+add[size];
					if(p>=131072||p<0)break;
					memo[next][p]+=memo[now][j]*((j>>slide[size])&mask[size])/all;
				}
			}
		}
		ans+=memo[next][2]+memo[next][8]+memo[next][64]+memo[next][2048];
	}
	std::cout<<"ans="<<ans;
 }

*問い151
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20151
封筒の中身の期待値を求める問題。


シンプルに動的計画法で期待値を求めるだけです。
丁寧ですがコードサイズが膨らみました。
この問題簡単すぎますが他の人のコードを読んでると楽しい問題です。
問題をどんな構造で解くか。
色々なとらえ方があって楽しいですね。




 #include<stdio.h>
 #include<map>
 #include<string.h>
 #include<iostream>
 #include<time.h>
 struct E{
	__int64 paper[6];
	bool operator<(const E& e)const{
		for(int i=1;i<=5;i++){
			if(paper[i]!=e.paper[i])return paper[i]<e.paper[i];
		}
		return false;
	}
	void print(){
		std::cout<<"(";
		for(int i=1;i<=5;i++){
			std::cout<<paper[i]<<" ";
		}
		std::cout<<")";
	}
 };
 int main(){
	double start=clock();
	double ans=0,perm,p;
	std::map<E,double> memo,next;
	std::map<E,double>::iterator it;
	E e,es[6];
	memset(e.paper,0,sizeof(e.paper));
	for(int i=1;i<=5;i++){
		es[i]=e;
		es[i].paper[i]=1;
	}
	e.paper[1]=1;
	memo[e]=1.0;	
	for(int i=1;i<=14;i++){
		for(it=memo.begin();it!=memo.end();it++){
			double paperCount=0;
			e=(*it).first;
			for(int j=1;j<=5;j++){
				paperCount+=e.paper[j];
			}
			if(paperCount==0)continue;
			for(int j=1;j<=5;j++){
				e=(*it).first;
				if(e.paper[j]<1)continue;
				e.paper[j]--;
				for(int k=j+1;k<=5;k++){
					e.paper[k]++;
				}
				if(next.find(e)==next.end())next[e]=0;
				next[e]+=(*it).second*(e.paper[j]+1.0)/paperCount;
			}
		}
		memo.clear();
		memo.insert(next.begin(),next.end());
		next.clear();
		for(int i=1;i<=5;i++){
			ans+=memo[es[i]];
		}
		std::cout<<i+1<<" "<<ans<<" "<<memo.size()<<"\n";
	}
	std::cout<<"ans="<<ans<<" time="<<clock()-start;
 }


他の人のコードを参考にショートコードを作ってみました。
私はショートコードに向いてないなと痛感した次第です。

 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 double memo[2][131072]={{0,1.0,0},{0}};
 int main(){
	double ans=0,all;
	int slide[]={0,1,3,6,11},mask[]={1,3,7,31,63},add[]={2121,2118,2104,1984,-2048};
	for(int i=1;i<=14;i++){
		int now=(i+1)&1,next=i&1;
		memset(memo[next],0,sizeof(memo[next]));
		for(int j=0;j<131072;j++){
			all=0;
			for(int size=0;size<5;size++)all+=(j>>slide[size])&mask[size];
			for(int size=0;size<5;size++){
				if(((j>>slide[size])&mask[size])!=0){
					int p=j+add[size];
					if(p>=131072||p<0)break;
					memo[next][p]+=memo[now][j]*((j>>slide[size])&mask[size])/all;
				}
			}
		}
		ans+=memo[next][2]+memo[next][8]+memo[next][64]+memo[next][2048];
	}
	std::cout<<"ans="<<ans;
 }




*問い154
(x+y+z)^20万乗を展開した時係数が１０＾１２乗の倍数になる計数の数を数える問題。

解法
２分で解けるコードを組めました。
２０万段目の組み合わせだけを計算します。
２０万段目の一番外の列を計算すれば２０万段目の残りの列を求めることは簡単です
この時、２と5の倍数が１２個以上含まれる数だけが10＾12となります。
なので２と5の素因数だけを数えれば問題が解けます。





 #include<stdio.h>
 #include<iostream>
 #include<time.h>
 const int up=20*10000;
 int intFacts2[up+2]={0},intFacts5[up+2]={0};
 int row2[up+2]={0},row5[up+2]={0};
 int memo2[up+2]={0},memo5[up+2]={0};
 int factCount(int n,int fact){
	if(n<1)return 0;
	int count=0;
	while(n%fact==0){
		n/=fact;
		count++;
	}
	return count;
 }
 void setIntFacts2And5(){
	for(int i=2;i<=up;i++){
		int n=i;
		intFacts2[i]=factCount(n,2);
		intFacts5[i]=factCount(n,5);
	}
 }
 int main(){
	double start=clock();
	setIntFacts2And5();
	__int64 ans=0;
	for(int i=1;i<up;i++){
		row2[i]=(row2[i-1]+intFacts2[up-i+1]-intFacts2[i]);
		row5[i]=(row5[i-1]+intFacts5[up-i+1]-intFacts5[i]);
	}
	for(int i=1;i<=up;i++){
		for(int j=1;j<=i+1;j++){
			memo2[j]=memo2[j-1]+intFacts2[i-j+1]-intFacts2[j];
			memo5[j]=memo5[j-1]+intFacts5[i-j+1]-intFacts5[j];
			ans+=(memo2[j-1]+row2[i]>=12&&memo5[j-1]+row5[i]>=12);
		}
	}
	std::cout<<"\nans="<<ans<<"\ntime="<<clock()-start;
 }