「オイラープロジェクト110~120」の編集履歴(バックアップ)一覧はこちら
オイラープロジェクト110~120 - (2012/09/10 (月) 13:46:43) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い113
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 1010未満では277032個しかない.
googol数 (10100) 未満ではずみ数でないものの数を答えよ.
増加数も減少数も2桁目からしか意味がないので1桁目を設定して後は条件を満たすように動的計画法で一ケタずつ求めていきます。
500桁の数のうち指定された範囲内にあるジグザグ数の数を求める問題に比べたら楽勝でした。
#include<stdio.h>
#include<string.h>
#include<iostream>
int main(){
__int64 uMemo[10],dMemo[10],uNext[10],dNext[10];
__int64 ansU=0,ansD=0;
memset(uMemo,0,sizeof(uMemo));
memset(dMemo,0,sizeof(dMemo));
for(int i=1;i<10;i++){
uMemo[i]=1;//
dMemo[i]=1;//1桁目の設定
}
int last=100;
for(int i=0;i<last-1;i++){
memset(uNext,0,sizeof(uNext));
memset(dNext,0,sizeof(dNext));
//左端の数字
for(int k=0;k<10;k++){
//前の桁の数字
for(int L=k;L<10;L++){
uNext[L]+=uMemo[k];
}
}
for(int k=0;k<10;k++){
for(int L=k;L>=0;L--){
//次の桁の数字
dNext[L]+=dMemo[k];
}
}
for(int j=0;j<10;j++){
//増加数を数え上げる
ansU+=uNext[j];
ansD+=dNext[j];
}
//増加数と減少数の重複分を引いて表示
std::cout<<ansU<<" "<<ansD<<" "<<ansU+ansD-i*9<<"\n";
memcpy(uMemo,uNext,sizeof(uNext));
memcpy(dMemo,dNext,sizeof(dNext));
}
}
*問い114
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20114
最初動的計画法で解こうと適当に書いてみるもプログラムのミスか少し取りこぼす数が出たので、まずは数字の変化を眺めようと30まで全探索。
全探索してみると驚くほど単純な漸化式が成り立つことが分かったので漸化式で解く。
#include<stdio.h>
#include<iostream>
int main(){
__int64 c,a=7,b=4,roop[]={0,-1,-1,0,1,1};
for(int i=6;i<=50;i++){
c=a+b+roop[(i-6)%6];
b=a;
a=c;
std::cout<<i<<","<<c<<"\n";
}
}
最初に軽く書いてみた取りこぼしの出る動的計画法。
軽く書いたとはいえn=8から謎の取りこぼしが出てくる?
何故だろう?
#include<stdio.h>
#include<iostream>
int main(){
__int64 memo[100]={0};
__int64 p,ans=0;
int up;
scanf("%d",&up);
for(int i=0;i<=up;i++){
p=memo[i]+1;
for(int k=i+4;k<=up+1;k++){
memo[k]+=p;
}
for(int j=0;j<=up+1;j++){
std::cout<<memo[j]<<" ";
}
std::cout<<"\n";
}
for(int i=0;i<=up+1;i++)ans+=memo[i];
std::cout<<ans+1;
}
下記はきちんと修正したコードで問い115用に少し改造を加えている。
メモ化で足すとき後ろの方で組み合わせ数がc*pで増えていくのに気づいてなかった。
この問題は丁寧に読解すれば高校レベルのようだ。
#include<stdio.h>
#include<iostream>
__int64 calc(int size,int up){
__int64 memo[101]={0},p,c;
size++;
for(int i=0;i<=up;i++){
p=memo[i]+1;
c=1;
for(int k=i+size;k<=up+1;k++){
memo[k]+=p*c;
c++;
}
}
return memo[up+1]+1;
}
int main(){
std::cout<<calc(3,29);
}
*問い115
長さnユニットからなる一列上に長さ50以上の棒を0以上入れていく。
この時可能な入れ方の組み合わせが100万を超える最小のnを求めよ。
114が出来たら後は簡単な問題です。
10分でプログラムできました。
#include<stdio.h>
#include<iostream>
__int64 calc(int size,int up){
__int64 memo[1001]={0},p,c;
size++;
for(int i=0;i<=up;i++){
p=memo[i]+1;
c=1;
for(int k=i+size;k<=up+1;k++){
memo[k]+=p*c;
c++;
}
}
return memo[up+1]+1;
}
int main(){
int i=50;
__int64 t;
while(1){
t=calc(50,i);
std::cout<<i<<" "<<t<<"\n";
if(t>1000000)break;
i++;
}
printf("%d",i);
}
*問い116
1種類なだけで問い117と同じ考え方で解ける。
一度解き方が分かれば5分で解ける問題。
#include<stdio.h>
#include<iostream>
int main(){
__int64 ans=0,p;
int up=50;
int size[]={2,3,4};
for(int i=0;i<3;i++){
__int64 memo[100]={0};
memo[0]=1;
for(int j=0;j<=up+1;j++){
p=memo[j];
ans+=p;
for(int k=j+size[i];k<=up;k++){
memo[k]+=p;
}
std::cout<<memo[j];
}
std::cout<<"\n";
}
std::cout<<ans-3<<"\n";
}
*問い117
長さ1の黒タイル、2の赤タイル、3の緑タイル、4の青タイルを長さ50の列に隙間なくはめていくとき何通りのはめかたがあるか。
黒を空白と考え他の色のタイルを左から順にはめていきます。
隙間があいても、一度置いたところより左にはもうはめないというルールでタイルを埋め込んでいきます。
このルールにしたがえば組み合わせが排他的的集合に分岐するので後はメモ化で一発の簡単な問題です。
調べ物なしで解法を自力で思いつくのに3時間かかりました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 memo[100]={0},ans=0;
memo[0]=1;
int up=50;
for(int i=0;i<=up;i++){
__int64 p=memo[i];//このマスまでどんなはめ方をしたかは関係なく何通りかだけが大事となる。
memo[i+2]+=p;//次に赤をはめた
memo[i+3]+=2*p;//一マスあけた赤か緑をはめ込むので2倍
for(int j=i+4;j<=up;j++){
memo[j]+=3*p;//2マス以上あけて赤か一ますあけて緑か青をはめ込むので3倍。
}
std::cout<<memo[i]<<"\n";//右側残り全部黒の場合を回収する
ans+=memo[i];
}
std::cout<<"\n"<<ans;
}
*問い118
1 から 9 の全ての数字を使い、自由につなげることで 10 進数の数字を作り、複数の集合を作ることができる。集合 {2,5,47,89,631} は面白いことに全ての要素が素数である。
1 から 9 の数字をちょうど 1 個ずつ含み、素数の要素しか含まない集合はいくつあるか?
解法
再帰関数を使って全探索します。
この時数字を繋げる、数字を切断するで分岐し、backで前作った数を記憶します。
前作った数より小さい数を作らないことで集合の重複を防ぎます。
#include<stdio.h>
#include<math.h>
bool checkSo(int n){
if(n==2)return true;
if(n<2 || n%2==0)return false;
int m=sqrt(n);
for(int i=3;i<=m;i+=2){
if(n%i==0)return false;
}
return true;
}
int ans=0;
int perm[10]={0};
void saiki(int num,int deep,int back){
if(deep==9&&num>back){
//ここまでの素数チェックを全て通過し最後の数も素数だった
ans+=checkSo(num);
}else{
//numにまだ足す
for(int i=1;i<10;i++){
if(perm[i]==0){
perm[i]=1;
saiki(num*10+i,deep+1,back);
perm[i]=0;
}
}
//足さないで次の数へ行く
if(checkSo(num)==true&&num>back){
for(int i=1;i<10;i++){
if(perm[i]==0){
perm[i]=1;
saiki(i,deep+1,num);
perm[i]=0;
}
}
}
}
}
int main(){
saiki(0,0,0);
printf("%d",ans);
}
*問い113
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 1010未満では277032個しかない.
googol数 (10100) 未満ではずみ数でないものの数を答えよ.
増加数も減少数も2桁目からしか意味がないので1桁目を設定して後は条件を満たすように動的計画法で一ケタずつ求めていきます。
500桁の数のうち指定された範囲内にあるジグザグ数の数を求める問題に比べたら楽勝でした。
#include<stdio.h>
#include<string.h>
#include<iostream>
int main(){
__int64 uMemo[10],dMemo[10],uNext[10],dNext[10];
__int64 ansU=0,ansD=0;
memset(uMemo,0,sizeof(uMemo));
memset(dMemo,0,sizeof(dMemo));
for(int i=1;i<10;i++){
uMemo[i]=1;//
dMemo[i]=1;//1桁目の設定
}
int last=100;
for(int i=0;i<last-1;i++){
memset(uNext,0,sizeof(uNext));
memset(dNext,0,sizeof(dNext));
//左端の数字
for(int k=0;k<10;k++){
//前の桁の数字
for(int L=k;L<10;L++){
uNext[L]+=uMemo[k];
}
}
for(int k=0;k<10;k++){
for(int L=k;L>=0;L--){
//次の桁の数字
dNext[L]+=dMemo[k];
}
}
for(int j=0;j<10;j++){
//増加数を数え上げる
ansU+=uNext[j];
ansD+=dNext[j];
}
//増加数と減少数の重複分を引いて表示
std::cout<<ansU<<" "<<ansD<<" "<<ansU+ansD-i*9<<"\n";
memcpy(uMemo,uNext,sizeof(uNext));
memcpy(dMemo,dNext,sizeof(dNext));
}
}
*問い114
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20114
最初動的計画法で解こうと適当に書いてみるもプログラムのミスか少し取りこぼす数が出たので、まずは数字の変化を眺めようと30まで全探索。
全探索してみると驚くほど単純な漸化式が成り立つことが分かったので漸化式で解く。
#include<stdio.h>
#include<iostream>
int main(){
__int64 c,a=7,b=4,roop[]={0,-1,-1,0,1,1};
for(int i=6;i<=50;i++){
c=a+b+roop[(i-6)%6];
b=a;
a=c;
std::cout<<i<<","<<c<<"\n";
}
}
最初に軽く書いてみた取りこぼしの出る動的計画法。
軽く書いたとはいえn=8から謎の取りこぼしが出てくる?
何故だろう?
#include<stdio.h>
#include<iostream>
int main(){
__int64 memo[100]={0};
__int64 p,ans=0;
int up;
scanf("%d",&up);
for(int i=0;i<=up;i++){
p=memo[i]+1;
for(int k=i+4;k<=up+1;k++){
memo[k]+=p;
}
for(int j=0;j<=up+1;j++){
std::cout<<memo[j]<<" ";
}
std::cout<<"\n";
}
for(int i=0;i<=up+1;i++)ans+=memo[i];
std::cout<<ans+1;
}
下記はきちんと修正したコードで問い115用に少し改造を加えている。
メモ化で足すとき後ろの方で組み合わせ数がc*pで増えていくのに気づいてなかった。
この問題は丁寧に読解すれば高校レベルのようだ。
#include<stdio.h>
#include<iostream>
__int64 calc(int size,int up){
__int64 memo[101]={0},p,c;
size++;
for(int i=0;i<=up;i++){
p=memo[i]+1;
c=1;
for(int k=i+size;k<=up+1;k++){
memo[k]+=p*c;
c++;
}
}
return memo[up+1]+1;
}
int main(){
std::cout<<calc(3,29);
}
*問い115
長さnユニットからなる一列上に長さ50以上の棒を0以上入れていく。
この時可能な入れ方の組み合わせが100万を超える最小のnを求めよ。
114が出来たら後は簡単な問題です。
10分でプログラムできました。
#include<stdio.h>
#include<iostream>
__int64 calc(int size,int up){
__int64 memo[1001]={0},p,c;
size++;
for(int i=0;i<=up;i++){
p=memo[i]+1;
c=1;
for(int k=i+size;k<=up+1;k++){
memo[k]+=p*c;
c++;
}
}
return memo[up+1]+1;
}
int main(){
int i=50;
__int64 t;
while(1){
t=calc(50,i);
std::cout<<i<<" "<<t<<"\n";
if(t>1000000)break;
i++;
}
printf("%d",i);
}
*問い116
1種類なだけで問い117と同じ考え方で解ける。
一度解き方が分かれば5分で解ける問題。
#include<stdio.h>
#include<iostream>
int main(){
__int64 ans=0,p;
int up=50;
int size[]={2,3,4};
for(int i=0;i<3;i++){
__int64 memo[100]={0};
memo[0]=1;
for(int j=0;j<=up+1;j++){
p=memo[j];
ans+=p;
for(int k=j+size[i];k<=up;k++){
memo[k]+=p;
}
std::cout<<memo[j];
}
std::cout<<"\n";
}
std::cout<<ans-3<<"\n";
}
*問い117
長さ1の黒タイル、2の赤タイル、3の緑タイル、4の青タイルを長さ50の列に隙間なくはめていくとき何通りのはめかたがあるか。
黒を空白と考え他の色のタイルを左から順にはめていきます。
隙間があいても、一度置いたところより左にはもうはめないというルールでタイルを埋め込んでいきます。
このルールにしたがえば組み合わせが排他的的集合に分岐するので後はメモ化で一発の簡単な問題です。
調べ物なしで解法を自力で思いつくのに3時間かかりました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 memo[100]={0},ans=0;
memo[0]=1;
int up=50;
for(int i=0;i<=up;i++){
__int64 p=memo[i];//このマスまでどんなはめ方をしたかは関係なく何通りかだけが大事となる。
memo[i+2]+=p;//次に赤をはめた
memo[i+3]+=2*p;//一マスあけた赤か緑をはめ込むので2倍
for(int j=i+4;j<=up;j++){
memo[j]+=3*p;//2マス以上あけて赤か一ますあけて緑か青をはめ込むので3倍。
}
std::cout<<memo[i]<<"\n";//右側残り全部黒の場合を回収する
ans+=memo[i];
}
std::cout<<"\n"<<ans;
}
*問い118
1 から 9 の全ての数字を使い、自由につなげることで 10 進数の数字を作り、複数の集合を作ることができる。集合 {2,5,47,89,631} は面白いことに全ての要素が素数である。
1 から 9 の数字をちょうど 1 個ずつ含み、素数の要素しか含まない集合はいくつあるか?
解法
再帰関数を使って全探索します。
この時数字を繋げる、数字を切断するで分岐し、backで前作った数を記憶します。
前作った数より小さい数を作らないことで集合の重複を防ぎます。
#include<stdio.h>
#include<math.h>
bool checkSo(int n){
if(n==2)return true;
if(n<2 || n%2==0)return false;
int m=sqrt(n);
for(int i=3;i<=m;i+=2){
if(n%i==0)return false;
}
return true;
}
int ans=0;
int perm[10]={0};
void saiki(int num,int deep,int back){
if(deep==9&&num>back){
//ここまでの素数チェックを全て通過し最後の数も素数だった
ans+=checkSo(num);
}else{
//numにまだ足す
for(int i=1;i<10;i++){
if(perm[i]==0){
perm[i]=1;
saiki(num*10+i,deep+1,back);
perm[i]=0;
}
}
//足さないで次の数へ行く
if(checkSo(num)==true&&num>back){
for(int i=1;i<10;i++){
if(perm[i]==0){
perm[i]=1;
saiki(i,deep+1,num);
perm[i]=0;
}
}
}
}
}
int main(){
saiki(0,0,0);
printf("%d",ans);
}
*問い119
512 という数は興味深い数である. というのも, 各桁の和を何乗かしたものに等しくなっているからである: 5 + 1 + 2 = 8, 83 = 512 である. この特性を持つ他の数は例えば 614656 = 284 である.
この数列の第 n 項を an と定義し, また 2 桁以上であるとしよう.
a2 = 512, a10 = 614656 となる.
a30 を求めよ.
整数m^bは密度が低いのでこれを利用して最初にこのb乗された数字だけを試すようにstd::setにリストを作ります。
後はsetの中身を一つずつ試すだけでまあ一応それなりの速度が出ますが、もっと賢い方法があるようです。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<set>
const __int64 up=100000000000;//とりあえず1000億までで様子見
__int64 wa(__int64 n){
__int64 re=0;
while(n!=0){
re+=n%10;
n/=10;
}
return re;
}
int main(){
__int64 a,b,c;
int count=0;
std::set<__int64> memo;
std::set<__int64>::iterator it;
for(__int64 i=2;i<=100000;i++){
a=b=i;
while(a<up){
a*=b;
memo.insert(a);
}
}
std::cout<<memo.size()<<"\n";
for(it=memo.begin();it!=memo.end();it++){
a=(*it);
c=b=wa(a);
while(b<a&&c!=1){
b*=c;
}
if(b==a){
count++;
std::cout<<count-3<<" "<<a<<" "<<c<<"\n";
}
}
}