問い51
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2051
*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)
解法
100万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタンを求めてその出現回数をカウントしてみました。
答えは正しいですし34秒で答えは出るのですが何か間違ったコードを書いてる感がすごくあります。
C++なら遅くても数秒程度で答えが出るコードが正しいコードのような気がします。
答えはもっとシンプル。
そんな気がするのでこの問題後日再チャレンジする予定です。
#include<stdio.h>
#include<map>
#include<string>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<set>
struct S{
int num,count;
};
std::set<std::string> patternSet;
std::map<std::string,S> memo;
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
void setMemo(char text[10],char num,int p,int n){
if(p==0)patternSet.clear();
if(num!=-1){
if(patternSet.find(text)==patternSet.end()){
patternSet.insert(text);
if(memo.find(text)==memo.end()){
S s;
s.count=1;
s.num=n;
memo[text]=s;
}else{
memo[text].count++;
}
}
}
if(text[p]=='\0')return;
if(num==-1){
setMemo(text,-1,p+1,n);
char c=text[p];
text[p]='*';
setMemo(text,c,p+1,n);
text[p]=c;
}else{
setMemo(text,num,p+1,n);
if(text[p]==num){
text[p]='*';
setMemo(text,num,p+1,n);
text[p]=num;
}
}
}
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;
}
}
}
int main(){
setSo();
int num;
std::string str,str2;
for(int i=0;i<sosuu.size();i++){
int p=sosuu[i];
char text[10];
sprintf(text,"%d",p);
setMemo(text,-1,0,p);
//std::cout<<"\n";
}
int ans=up+1;
std::cout<<memo["56**3"].count<<"\n";
for(std::map<std::string,S>::iterator it=memo.begin();it!=memo.end();it++){
if((*it).second.count==8&&ans>(*it).second.num){
ans=(*it).second.num;
}
}
printf("%d",ans);
}
問い52
解法
この問題は本当はコードを書くまでもなく1/7の性質について知っていたら簡単に解ける問題です。
一応コードを書いてみました。
#include<stdio.h>
int main(){
for(int i=2;i<10;i++){
int memo[7],num=1,count[10]={0};
bool ok=true;
for(int j=0;j<6;j++){
num*=10;
memo[j]=num/i;
num%=i;
if(count[num]==1)ok=false;
count[num]++;
}
if(num==1&&ok==true){
for(int j=0;j<6;j++)printf("%d",memo[j]);
break;
}
}
}
問い53
解法
パスカルの三角形を計算して100万以上になったらその影響下にある項は全て100万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。
一段ずつ上からパスカルの三角形に基づき計算します。
左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。
この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。
1段目0C0から計算が始まるので100Crだと101段目まで計算する点に注意するくらいです。
#include<stdio.h>
#include<string.h>
#include<time.h>
int main(){
double start=clock();
int memo[102]={0,1,0},ans=0;
for(int n=1;n<=101;n++){
int next[102]={0};
int r;
for(r=1;r<=n;r++){
next[r]=memo[r-1]+memo[r];
if(next[r]>=1000*1000)break;
}
if(r<n){
if(n%2==0){
ans+=(n/2-r+1)*2;
}else{
ans+=(n+1)/2==r?1:1+((n+1)/2-r)*2;
}
}
memcpy(memo,next,sizeof(next));
}
printf("ans=%d time=%lf",ans,clock()-start);
}
問い54
解法
役を判定する関数を全部書いて大きい役からチェックしスコアを算出してみました。
役の中で一番大きな数字をスコアに加算することでコードを少し簡略化したつもりです。
役の排他性を考えたポーカーの考案者は中々素晴らしいものがありますね。
スートで判定するということがないのでコードは少し簡単です。
#include<stdio.h>
#include<algorithm>
struct CARD{
int num;
char suit;
void set(char text[3]){
if(text[0]=='T'){
num=10;
}else if(text[0]=='J'){
num=11;
}else if(text[0]=='Q'){
num=12;
}else if(text[0]=='K'){
num=13;
}else if(text[0]=='A'){
num=14;//1は一番大きな数として扱う
}else{
num=text[0]-'0';
}
suit=text[1];
}
bool operator<(const CARD& c)const{
if(c.num!=num)return num<c.num;
return suit<c.suit;
}
};
CARD cardsA[5],cardsB[5];
int onePairs(CARD cards[5]){
int point=1000;
for(int i=0;i<4;i++){
if(cards[i].num==cards[i+1].num)return point+cards[i].num;
}
return 0;
}
int TwoPairs(CARD cards[5]){
int point=2000;
if(cards[0].num==cards[1].num){
if(cards[2].num==cards[3].num){
return point+cards[3].num;
}
if(cards[3].num==cards[4].num){
return point+cards[3].num;
}
}
if(cards[1].num==cards[2].num&&cards[3].num==cards[4].num){
return point+cards[3].num;
}
return 0;
}
int ThreeOfAKind(CARD cards[5]){
int point=3000;
if(cards[0].num==cards[2].num||cards[1].num==cards[3].num||cards[2].num==cards[4].num){
return point+cards[2].num;
}
return 0;
}
int Straight(CARD cards[5]){
int point=4000;
int num=cards[0].num;
for(int i=1;i<5;i++){
num++;
if(cards[i].num!=num)return 0;
}
return point+cards[4].num;
}
int flash(CARD cards[5]){
int point=5000;
if(cards[0].suit==cards[1].suit&&cards[1].suit==cards[2].suit&&cards[2].suit==cards[3].suit&&cards[3].suit==cards[4].suit){
return point+cards[4].num;
}
return 0;
}
int FullHouse(CARD cards[5]){
int point=6000;
if(cards[0].num==cards[1].num&&cards[2].num==cards[4].num)return point+cards[2].num;
if(cards[0].num==cards[2].num&&cards[3].num==cards[4].num)return point+cards[3].num;
return 0;
}
int FourOfAKind(CARD cards[5]){
int point=7000;
if(cards[0].num==cards[3].num){
return point+cards[0].num;
}
if(cards[1].num==cards[4].num){
return point+cards[1].num;
}
return 0;
}
int StraightFlush(CARD cards[5]){
int point=8000;
if(flash(cards)!=0&& Straight(cards)!=0){
return point+cards[4].num;
}
return 0;
}
int RoyalFlush(CARD cards[5]){
int point=9000;
if(flash(cards)!=0&&cards[0].num==10&&cards[1].num==11&&cards[2].num==12&&cards[3].num==13&&cards[4].num==14){
return point+14;
}
return 0;
}
int calc(CARD cards[5]){
int point;
if((point=RoyalFlush(cards))!=0)return point;
if((point=StraightFlush(cards))!=0)return point;
if((point=FourOfAKind(cards))!=0)return point;
if((point=FullHouse(cards))!=0)return point;
if((point=flash(cards))!=0)return point;
if((point=Straight(cards))!=0)return point;
if((point=ThreeOfAKind(cards))!=0)return point;
if((point=TwoPairs(cards))!=0)return point;
if((point=onePairs(cards))!=0)return point;
return 0;
}
int lastCheck(CARD cardsA[5],CARD cardsB[5]){
for(int i=4;i>=0;i--){
if(cardsA[i].num>cardsB[i].num)return 1;
if(cardsA[i].num<cardsB[i].num)return -1;
}
return 0;
}
void print(CARD cards[5]){
printf("(");
for(int i=0;i<5;i++)printf("%d%c ",cards[i].num,cards[i].suit);
printf(")");
}
int main(){
char c[3],c1;
int ans=0;
while(1){
bool last=false;
for(int i=0;i<5;i++){
if(scanf("%s",c)==EOF){
last=true;
break;
}
cardsA[i].set(c);
}
if(last==true)break;
for(int i=0;i<5;i++){
scanf("%s",c);
cardsB[i].set(c);
}
std::sort(cardsA,cardsA+5);
std::sort(cardsB,cardsB+5);
//print(cardsA);
//print(cardsB);
int p1=calc(cardsA);
int p2=calc(cardsB);
//printf("(%d %d)\n",p1,p2);
if(p1==p2)p1+=lastCheck(cardsA,cardsB);
if(p1>p2)ans++;
}
printf("ans%d",ans);
}
問い55
解法
定義通り素朴に計算してみました。
(defun toRev(n)
(parse-integer (reverse (princ-to-string n))))
(let ((a) (ans 0))
(dotimes (i 9999)
(setq a (+ 1 i))
(dotimes (j 50)
(setq a (+ a (toRev a)))
(if (= a (toRev a))
(setq ans (+ ans 1) j 50)
)))(- 9999 ans))
問い56
a^b (a,b<100の自然数)として各桁の和の最大値を求めよ。
解法
Lispで力づくで解いてました。
賢い方法ありますかね、これ。
(defun ketaSum(n)
(apply #'+ (map 'list #'digit-char-p (princ-to-string n))))
(let ((ans 0) (a 0))
(dotimes (i 99)
(dotimes (j 99)
(setq a (ketaSum (expt (+ 1 i) (+ 1 j))))
(if (< ans a)
(setq ans a)
)))ans)
問い57
解法
数式をそのまま再帰式になおすだけです。
saikl関数が数式を表します。
一番底が5/2で始まり再帰を戻るたびに項が大きくなっていきます。
(defvar ans 0)
(defun saiki(deep)
(let ((a 0) (re 0))
(if (= deep 1000)
(setq a (/ 5 2))
(setq a (+ 2 (/ 1 (saiki (+ 1 deep))))))
(setq ans (+ ans (check (- a 1))))a))
saiki
(defun check (n) (let ((a (numerator n))
(b (denominator n))
(re 0))
(if (< (length (princ-to-string b)) (length (princ-to-string a)))
(setq re 1)
(setq re 0))re))
saiki
(defun main()
(setq ans 0)
(saiki 0) ans)
(main )
問い58
#include<stdio.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
int all=0,count=0,size=3,num=1;
while(1){
for(int i=0;i<4;i++){
num+=size-1;
if(isPrime(num)==true)count++;
}
all+=4;
if(count*10<=all)break;
size+=2;
}
printf("%d",size);
}
問い60
解法
全然だめです、賢い解法思いつきません。
素数を点、結合可能な素数の組を線からなるグラフとみて、3万以下の素数についてグラフが五望星をなしている場所を探索で探してみましたがコードは膨らむし速度は出ないしで駄目ですね。
グラフの生成部分が物凄く遅くc++なのに答えを出すのに34秒もかかってます。
こんなコードではプロジェクトオイラーでは負け組みな気がします。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<map>
#include<stdlib.h>
#include<set>
#include<string.h>
#include<string>
#include<time.h>
const int up=100000;
std::vector<__int64> sosuu;
bool isPrime[up+1];
std::map<int,std::set<int> > cons;
int ans=0;
void setPrime(){
int i2;
memset(isPrime,true,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=4;i<=up;i+=2)isPrime[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(isPrime[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
isPrime[j]=false;
}
}
}
bool checkPrime(__int64 n){
if(n<2)return false;
for(int i=0;sosuu[i]*sosuu[i]<=n;i++){
if(n%sosuu[i]==0)return false;
}
return true;
}
void setConnect(){
char text[20];
__int64 a,b;
for(int i=0;sosuu[i]<=30000;i++){
for(int j=i+1;sosuu[j]<=30000;j++){
sprintf(text,"%I64lld%I64lld",sosuu[i],sosuu[j]);
sscanf(text,"%I64lld",&a);
sprintf(text,"%I64lld%I64lld",sosuu[j],sosuu[i]);
sscanf(text,"%I64lld",&b);
if(checkPrime(a)==true&&checkPrime(b)==true){
cons[sosuu[i]].insert(sosuu[j]);
}
}
}
}
bool addOK(std::set<int>& perm,int addNum){
for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
if(cons[(*it)].find(addNum)==cons[(*it)].end())return false;
}
return true;
}
void print(std::set<int> perm,int num){
printf("解候補の組(%d ",num);
for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
printf("%d ",(*it));
}
printf(")\n");
}
void saiki(int num,std::set<int>::iterator it,int count,int wa,std::set<int>& perm){
if(ans!=0&&ans<=wa)return;
if(count==4){
print(perm,num);
ans=wa;
return;
}
int wa2;
if(count!=0)it++;
for(;it!=cons[num].end();it++){
if(addOK(perm,(*it))==true){
wa2=wa+(*it);
perm.insert(*it);
saiki(num,it,count+1,wa2,perm);
perm.erase(*it);
}
}
}
int main(){
double start=clock();
setPrime();
printf("処理0終了\n");
setConnect();
printf("処理1終了 サイズ%d\n",cons.size());
std::set<int> perm;
for(std::map<int,std::set<int> >::iterator it=cons.begin();it!=cons.end();it++){
if((*it).second.size()>3)saiki((*it).first,(*it).second.begin(),0,(*it).first,perm);
}
printf("\nans=%d time=%lf",ans,clock()-start);
}
最終更新:2012年12月27日 20:54