*問い181 問題文と２時間ほどにらめっこして到達した答え。 整数論の授業は人生で一度も受けたことがないのでまあ頑張ってアルゴリズムをひとりで考えてみた。 BWの組み合わせに番号を振って、黒白の石の数とセットを小さいほうからメモ化で積み上げていくコード。 memo[黒石の数][白石の数][この組でのBWのセットの最大値]であとはこれをメモ化を使いながら動的計画法でアセプト。 コード実行時間５秒。 まあまあだと思う。 必要のなさそうなループが一か所あるようなのでそこを削れれば今のコードより１０００倍くらい早くなるかも？ 調べて解くより自分で考えて解く方が楽しいというのはプログラマ（プロアマとわず）としては完全に欠点だな。 プログラマは自分で考えるより調べて応用できる方が重要だもの、俺はプロのプログラマにはなれない。 #include<stdio.h> #include<string.h> #include<iostream> const int bSize=60; const int wSize=40; const int hashSize=(bSize+1)*(wSize+1); __int64 memo[bSize+1][wSize+1][hashSize+1]; void calc(int b,int w){ __int64 temp; for(int i=1;i<hashSize;i++){ int b1=i/(wSize+1); int w1=i%(wSize+1); temp=0; if(b>=b1&&w>=w1){ //解いただけでアップアップ状態だけど、このループ、ループなしで計算できるかも？ for(int j=0;j<=i;j++){ temp+=memo[b-b1][w-w1][j]; } memo[b][w][i]=temp; } } } int main(){ memset(memo,0,sizeof(memo)); memo[0][0][0]=1; __int64 ans=0; for(int b=0;b<=bSize;b++){ for(int w=0;w<=wSize;w++){ calc(b,w); } } for(int i=1;i<hashSize;i++){ ans+=memo[bSize][wSize][i]; std::cout<<memo[bSize][wSize][i]<<"\n"; } std::cout<<ans; } *問い185 Number Mind は, 有名なゲームMaster Mindの変種である. 色つきのペグの代わりに, 秘密の数字を推理する. 推理するごとに, 正しい桁がいくつあったかのみが伝えられる. つまり, 答えが1234で, 2036と推理した場合, 1つの桁が正しいと伝えられる. 数字は正しいが場所が違うということは伝えられない. 例えば, 以下の5桁の推理では, 90342 ;2 桁正しい 70794 ;0 桁正しい 39458 ;2 桁正しい 34109 ;1 桁正しい 51545 ;2 桁正しい 12531 ;1 桁正しい 答えの数字は39542の唯一つとなる. 以下の推理に基づいて, 5616185650518293 ;2 桁正しい 3847439647293047 ;1 桁正しい 5855462940810587 ;3 桁正しい 9742855507068353 ;3 桁正しい 4296849643607543 ;3 桁正しい 3174248439465858 ;1 桁正しい 4513559094146117 ;2 桁正しい 7890971548908067 ;3 桁正しい 8157356344118483 ;1 桁正しい 2615250744386899 ;2 桁正しい 8690095851526254 ;3 桁正しい 6375711915077050 ;1 桁正しい 6913859173121360 ;1 桁正しい 6442889055042768 ;2 桁正しい 2321386104303845 ;0 桁正しい 2326509471271448 ;2 桁正しい 5251583379644322 ;2 桁正しい 1748270476758276 ;3 桁正しい 4895722652190306 ;1 桁正しい 3041631117224635 ;3 桁正しい 1841236454324589 ;3 桁正しい 2659862637316867 ;2 桁正しい 16桁の唯一つの答えの数字を答えよ. 解法 賢い方法を思いつかなかったのでまずは答えだけもとめようと思い２重再帰の全探索で答えを求めてみました。 答えが一つであることを利用してsaiki関数の最後のcheck処理で少しずるをしています。 答えが複数になる場合はもう少し工夫が必要です。 #include<stdio.h> #include<string.h> void saiki(int deep,char commits[17]); int size; bool last=false; int outs[17][10]; struct D{ char text[17]; int hit; D(char t[17],int h){ for(int i=0;i<17;i++)text[i]=t[i]; hit=h; } }; D datas[]= { D("5616185650518293",2), D("3847439647293047",1), D("5855462940810587",3), D("9742855507068353",3), D("4296849643607543",3), D("3174248439465858",1), D("4513559094146117",2), D("7890971548908067",3), D("8157356344118483",1), D("2615250744386899",2), D("8690095851526254",3), D("6375711915077050",1), D("6913859173121360",1), D("6442889055042768",2), D("2321386104303845",0), D("2326509471271448",2), D("5251583379644322",2), D("1748270476758276",3), D("4895722652190306",1), D("3041631117224635",3), D("1841236454324589",3), D("2659862637316867",2) }; void saiki2(int deep,int p,char commits[17],int commit){ if(commit>datas[deep].hit)return; if(p==16){ if(commit!=datas[deep].hit)return; saiki(deep+1,commits); return; } char c1=datas[deep].text[p],c2=commits[p]; if(c2=='a'){ if(outs[p][c1-'0']==0&&commit<datas[deep].hit){ commits[p]=c1; saiki2(deep,p+1,commits,commit+1); commits[p]='a'; } if(last==true)return; outs[p][c1-'0']++; saiki2(deep,p+1,commits,commit); outs[p][c1-'0']--; }else{ if(c1==c2){ saiki2(deep,p+1,commits,commit+1); }else{ saiki2(deep,p+1,commits,commit); } } } void check(char commits[17]){ for(int i=0;i<size;i++){ if(commits[i]=='a'){ for(int j=0;j<10;j++){ if(outs[i][j]==0)commits[i]='0'+j; } } } } void saiki(int deep,char commits[17]){ if(deep>=size){ check(commits); printf("ans=%s\n",commits); last=true; return; } //int a; //printf("(%d %s)",deep,commits); //scanf("%d",&a); saiki2(deep,0,commits,0); } int main(){ size=sizeof(datas)/sizeof(D); //printf("%s %d\n",datas[1].text,datas[1].hit); char commits[17]; memset(commits,'a',sizeof(commits)); memset(outs,0,sizeof(outs)); commits[16]='\0'; saiki(0,commits); } *問い187 http://projecteuler.net/problem=187 解法 ええと余りよくないコードです。 何の工夫もなく全探索してるだけで遅いです。 一億くらいなら扱う数字も小さいからいけるかと思ったのですが意外と時間かかりました。 反面教師にしかならないコードですね。 #include<stdio.h> #include<vector> const int up=11000; std::vector<int> sosuu; bool so[up+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 check(int n){ int a,count=0; for(int i=0;i<sosuu.size();i++){ a=sosuu[i]; while(n%a==0){ count++; n/=a; if(count>1)break; } if(count>1)break; } if(n!=1)count++; return count==2; } int main(){ setSo(); int ans=0; for(int n=1;n<10000*10000;n++){ ans+=(check(n)); } printf("%d",ans); } *問い188 1777↑↑1855の最後の8桁を求めよ. 人生で初めてみる演算子というか相変わらず整数論の教育を人生で一度も受けたことがなかったので、どんな概念かわからなかったのですが、とりあえず乗算の周期性を利用して３０分ほどひとりで考えてコードを書いて解いてみました。 整数論について知らず調べ物もせず書いたコードなので多分効率の悪いコードだと思う。 今のところコード実行時間は2.043秒。 #include<stdio.h> #include<set> #include<map> #include<iostream> __int64 size,mod=100000000; std::set<int> memo; std::map<int,int> toNum; __int64 hp(__int64 a,__int64 k){ if(k==1)return a; return toNum[(int)hp(a,k-1)%size]; } int main(){ __int64 a=1777,b=a; toNum[0]=1; while(memo.find(b)==memo.end()){ memo.insert(b); b=(b*a)%mod; } b=1; size=memo.size(); for(int no=0;no<size;no++){ toNum[no]=b; b=(b*a)%size; } __int64 k=hp(a,1854); b=1; for(int i=0;i<k;i++)b=(b*a)%mod; std::cout<<"ans="<<b; }
