問い345
解法
動的計画法で一発です。
こういう簡単な問題ばかりならいいんだけど、難しい問題ばかり並んでるよな、、、
#include<stdio.h>
#include<string.h>
#include<iostream>
const int up=2<<14;
int memo[up][15],next[up][15];
int main(){
int data[15],nextP;
for(int r=0;r<15;r++){
for(int c=0;c<15;c++){
scanf("%d",&data[c]);
if(r==0)memo[(1<<c)][c]=data[c];
}
if(r==0)continue;
memset(next,0,sizeof(next));
for(int p=0;p<up;p++){
for(int c=0;c<15;c++){
if(memo[p][c]==0)continue;
for(int nc=0;nc<15;nc++){
if((p&(1<<nc))==0){
next[p|(1<<nc)][nc]=std::max(next[p|(1<<nc)][nc],memo[p][c]+data[nc]);
}
}
}
}
memcpy(memo,next,sizeof(next));
}
int ans=0;
for(int c=0;c<15;c++){
ans=std::max(memo[up-1][c],ans);
}
printf("%d",ans);
}
問い346
7という数字は特別な数字である, なぜなら7は2進数では111と表せ, また6進数では11と表せる.
(すなわち (7,10) = (11,6) = (111,2)). 別の言い方をすると, 7は少なくとも二種類の1より大きい底の記数法でレピュニット(全ての桁が1である自然数)であるという.
ここで上記の特徴を有する正の整数を「強いレピュニット」と呼ぶことにする. 50未満には8つの強いレピュニットが存在する. :{1,7,13,15,21,31,40,43}.
さらに, 1000未満の強いレピュニットの和は15864になる.
10^12未満の強いレピュニットの和を求めよ.
解法
どの数nもn-1進数で表現すれば11で必ず一個はレピュユニットになります。
そして基数iが10^6を超えると(11,i-1)は10^12未満ですが111は10^12を超えます。
つまり基数iが10^6を超えると11か1の2通りしか生成できません。
これを利用して10^6未満から作れるレピュユニットな数を試し、最後の集計で基数i>10^6による生成を足しこめば簡単に答えがもとまります。
他の人の解法はもっと賢いようでphtyonで0.078sec叩きだしてて私はもっと勉強が必要なようです。
#include<stdio.h>
#include<map>
#include<math.h>
#include<iostream>
int main(){
__int64 limit=1,sq,ans=0;
std::map<__int64,int> memo;
for(int i=0;i<12;i++)limit*=10;
sq=sqrt(limit);
for(__int64 i=2;i<=sq;i++){
__int64 num=1;
while(num<limit){
if(memo.find(num)==memo.end())memo[num]=0;
memo[num]++;
num=num*i+1;
}
}
std::cout<<"\n"<<memo.size()<<"\n";
for(std::map<__int64,int>::iterator it=memo.begin();it!=memo.end();it++){
int t=(*it).first>sq+1;
if(((*it).second+t)>1){
ans+=(*it).first;
}
}
std::cout<<"\nans"<<ans;
}
最終更新:2012年11月19日 10:50