「オイラープロジェクト151～160」の編集履歴（バックアップ）一覧に戻る
*問い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;
}
