立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
解法
3乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。
例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。
最初に5個Hitした辞書順があればそれが答えです。
集計で新しい辞書順が出てきたらその時に3乗の数字をカウンタに保管しておきます。
注意深く考えると、ある桁で答えが見つかってもその次の桁に行くまでにより小さな答えが見つからないか、先に6個以上が見つからないかチェックするかそれが不要なことを証明する必要がありますが。
答えが出たのでこれでもいいかと考えます。
プロジェクトオイラーは趣味のサイト、仕事ではないので気楽に解きます。
正確な回答はn^3と(n-1)^3の桁数が違ったときに、その時に5つと数えられているものがあればその集合を全て求めてその中で最小のものを答えとする必要があります。
numToList(N,Result):-!,
N3 is N*N*N,
number_chars(N3,List),
msort(List,Result).
search(N,Counts,N3):-
numToList(N,List),
member([4,List,N3],Counts),
!.
search(N,Counts,Result):-
numToList(N,List),
select([C,List,N3],Counts,Counts1),
!,
N1 is N+1,
C1 is C+1,
search(N1,[[C1,List,N3]|Counts1],Result).
search(N,Counts,Result):-
!,
N1 is N+1,
N3 is N^3,
numToList(N,List),
search(N1,[[1,List,N3]|Counts],Result).
main62:-
search(1,[],Ans),write(Ans).
C++で書き直した正しいコード。
リストをstd::mapに書き換えた結果
計算量も log2(n)/nだけ低減している。
桁数の計算で微妙な誤差が出る可能性があるので少しマージンを取っています。
#include<stdio.h>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<set>
struct S{
__int64 N3;
std::vector<char> zisyo;
bool operator<(const S& s)const{
return zisyo<s.zisyo;
}
void setN(__int64 N){
N3 = N;
zisyo.clear();
while(N>0){
zisyo.push_back(N%10+'0');
N/=10;
}
std::sort(zisyo.begin(),zisyo.end());
}
};
int main(){
std::map<S,int> memo;
std::map<S,int>::iterator mIt;
std::set<__int64> tempAns;
S s1;
for(__int64 i=4;;i++){
__int64 N3A =i*i*i;
__int64 N3B =(i-3)*(i-3)*(i-3);
int ketaA=floor(log(N3A)/log(10));
int ketaB=floor(log(N3B)/log(10));
if(ketaA>ketaB&&tempAns.size()>0){
break;
}else{
s1.setN(N3A);
if(memo.find(s1)==memo.end())memo[s1]=0;
memo[s1]++;
mIt=memo.lower_bound(s1);
s1=(*mIt).first;
int c=(*mIt).second;
if(c==5)tempAns.insert(s1.N3);
if(c>5)tempAns.erase(s1.N3);
}
}
for(std::set<__int64>::iterator it=tempAns.begin();it!=tempAns.end();it++){
std::cout<<(*it)<<" ";
}
}
最終更新:2014年02月20日 14:43