「オイラープロジェクト341～350」の編集履歴（バックアップ）一覧はこちら
「オイラープロジェクト341～350」(2012/11/19 (月) 10:50:39) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い345
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20345
行と列それぞれで1つのみの要素を選択した場合の要素の合計が最も大きくなるものを、その行列の「行列計( Matrix Sum )」と定義する。例えば、下記の行列での行列計は3315になる。( = 863 + 383 + 343 + 959 + 767) :
以下略
解法
動的計画法で一発です。
こういう簡単な問題ばかりならいいんだけど、難しい問題ばかり並んでるよな、、、
#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-1進数で表現すれば11で必ず一個はレピュユニットになります。
そして基数iが10＾6を超えると(11,i-1)は10＾12未満ですが111は10＾12を超えます。
つまり基数iが10＾6を超えると11か1の２通りしか生成できません。
これを利用して10＾6未満から作れるレピュユニットな数を試し、最後の集計で基数i>10^6による生成を足しこめば簡単に答えがもとまります。
#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;
}
*問い345
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20345
行と列それぞれで1つのみの要素を選択した場合の要素の合計が最も大きくなるものを、その行列の「行列計( Matrix Sum )」と定義する。例えば、下記の行列での行列計は3315になる。( = 863 + 383 + 343 + 959 + 767) :
以下略
解法
動的計画法で一発です。
こういう簡単な問題ばかりならいいんだけど、難しい問題ばかり並んでるよな、、、
#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-1進数で表現すれば11で必ず一個はレピュユニットになります。
そして基数iが10＾6を超えると(11,i-1)は10＾12未満ですが111は10＾12を超えます。
つまり基数iが10＾6を超えると11か1の２通りしか生成できません。
これを利用して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;
}
