「オイラープロジェクト110～120」の編集履歴（バックアップ）一覧はこちら
「オイラープロジェクト110～120」(2012/09/12 (水) 20:01:29) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い113
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 1010未満では277032個しかない.
googol数 (10100) 未満ではずみ数でないものの数を答えよ.
増加数も減少数も２桁目からしか意味がないので１桁目を設定して後は条件を満たすように動的計画法で一ケタずつ求めていきます。
昔５００桁までの数のうち指定された範囲内にあるジグザグ数の数を求めるという問題を解いたことがあるのですがそれに比べたら楽勝でした。
#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用に少し改造を加えている。
メモ化で足すとき後ろの方で組み合わせ数がｃ*ｐで増えていくのに気づいてなかった。
この問題は丁寧に読解すれば高校レベルのようだ。
#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
長さｎユニットからなる一列上に長さ50以上の棒を0以上入れていく。
この時可能な入れ方の組み合わせが１００万を超える最小のｎを求めよ。
114が出来たら後は簡単な問題です。
１０分でプログラムできました。
#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と同じ考え方で解ける。
一度解き方が分かれば５分で解ける問題。
#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の黒タイル、２の赤タイル、３の緑タイル、4の青タイルを長さ50の列に隙間なくはめていくとき何通りのはめかたがあるか。
黒を空白と考え他の色のタイルを左から順にはめていきます。
隙間があいても、一度置いたところより左にはもうはめないというルールでタイルを埋め込んでいきます。
このルールにしたがえば組み合わせが排他的的集合に分岐するので後はメモ化で一発の簡単な問題です。
調べ物なしで解法を自力で思いつくのに３時間かかりました。
#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;//一マスあけた赤か緑をはめ込むので２倍
for(int j=i+4;j<=up;j++){
memo[j]+=3*p;//2マス以上あけて赤か一ますあけて緑か青をはめ込むので３倍。
}
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";
}
}
}
*問い120
(a-1)n+(a+1)n を a2 で割った余りを r と定義する。
例えば、 a=7, n=3 の時、 r=42 である: 63 + 83 = 728 ≡ 42 mod 49。 n が変われば r も変わるが、 a=7 の時 r の最大値 rmax は 42 であることがわかる。
3 ≤ a ≤ 1000 において、 Σ rmax を求めよ。
(a-1)^nと(a+1)^nを毎回個別にモードを取ってから合計してモードを取っても答えが変わらず、モードを取るのですからどこかで周回することを利用して解きます。
モード演算で解ける問題は大抵力押しで解けるのがありがたいですね。
#include<stdio.h>
#include<iostream>
#include<set>
struct S{
__int64 am,ap;
bool operator<(const S& s)const{
if(am!=s.am)return am<s.am;
return ap<s.ap;
}
};
__int64 calc(__int64 a){
__int64 a2=a*a,ans=-1,t,ap=a+1,am=a-1;
S s;
s.am=a-1;
s.ap=a+1;
std::set<S> memo;
while(memo.find(s)==memo.end()){
memo.insert(s);
t=(s.am+s.ap)%a2;
if(t>ans){
ans=t;
}
s.am=(s.am*am)%a2;
s.ap=(s.ap*ap)%a2;
//std::cout<<t<<" "<<s.am<<" "<<s.ap<<"\n";
}
return ans;
}
int main(){
__int64 ans=0,t;
for(int i=3;i<1001;i++){
t=calc(i);
std::cout<<i<<" "<<t<<"\n";
ans+=t;
}
std::cout<<ans<<"\n";
}
*問い112
左から右までどの桁もその左の桁を上回らない数を増加数と呼ぶ。例えば、134468。
同様に、どの桁もその右の桁を上回らない数を減少数と呼ぶ。例えば、66420。
増加数でも減少数でもない正の整数を「活発な」数と呼ぶことにする。例えば、155349。
100以下の数に活発な数が無いのは明らかだが、1000より下の数では半数を少し上回る数(525)が活発である。
実際、活発な数の割合が50%に達する最少の数は538である。
驚くべきことに、活発な数はますます一般的になり、21780では活発な数の割合は90%に達する。
活発な数が数の割合が99%ちょうどになる最小の数を求めよ。
簡単な問題でアセプト稼ぐだけかな。
プルートゥース(力づくポパイに出てきたあれもプルートス)でない方法ってどんなだろ？
#include<stdio.h>
bool isUp(int n){
int a,b;
a=n%10;
n/=10;
while(n!=0){
b=n%10;
if(a<b)return false;
a=b;
n/=10;
}
return true;
}
bool isDown(int n){
int a,b;
a=n%10;
n/=10;
while(n!=0){
b=n%10;
if(a>b)return false;
n/=10;
a=b;
}
return true;
}
int main(){
int a=100,i=101;
while(1){
a+=(isUp(i)||isDown(i));
if(a*100==i)break;
i++;
}
printf("%d %d %d",i,a,a*100);
}
*問い113
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 1010未満では277032個しかない.
googol数 (10100) 未満ではずみ数でないものの数を答えよ.
増加数も減少数も２桁目からしか意味がないので１桁目を設定して後は条件を満たすように動的計画法で一ケタずつ求めていきます。
昔５００桁までの数のうち指定された範囲内にあるジグザグ数の数を求めるという問題を解いたことがあるのですがそれに比べたら楽勝でした。
#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用に少し改造を加えている。
メモ化で足すとき後ろの方で組み合わせ数がｃ*ｐで増えていくのに気づいてなかった。
この問題は丁寧に読解すれば高校レベルのようだ。
#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
長さｎユニットからなる一列上に長さ50以上の棒を0以上入れていく。
この時可能な入れ方の組み合わせが１００万を超える最小のｎを求めよ。
114が出来たら後は簡単な問題です。
１０分でプログラムできました。
#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と同じ考え方で解ける。
一度解き方が分かれば５分で解ける問題。
#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の黒タイル、２の赤タイル、３の緑タイル、4の青タイルを長さ50の列に隙間なくはめていくとき何通りのはめかたがあるか。
黒を空白と考え他の色のタイルを左から順にはめていきます。
隙間があいても、一度置いたところより左にはもうはめないというルールでタイルを埋め込んでいきます。
このルールにしたがえば組み合わせが排他的的集合に分岐するので後はメモ化で一発の簡単な問題です。
調べ物なしで解法を自力で思いつくのに３時間かかりました。
#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;//一マスあけた赤か緑をはめ込むので２倍
for(int j=i+4;j<=up;j++){
memo[j]+=3*p;//2マス以上あけて赤か一ますあけて緑か青をはめ込むので３倍。
}
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";
}
}
}
*問い120
(a-1)n+(a+1)n を a2 で割った余りを r と定義する。
例えば、 a=7, n=3 の時、 r=42 である: 63 + 83 = 728 ≡ 42 mod 49。 n が変われば r も変わるが、 a=7 の時 r の最大値 rmax は 42 であることがわかる。
3 ≤ a ≤ 1000 において、 Σ rmax を求めよ。
(a-1)^nと(a+1)^nを毎回個別にモードを取ってから合計してモードを取っても答えが変わらず、モードを取るのですからどこかで周回することを利用して解きます。
モード演算で解ける問題は大抵力押しで解けるのがありがたいですね。
#include<stdio.h>
#include<iostream>
#include<set>
struct S{
__int64 am,ap;
bool operator<(const S& s)const{
if(am!=s.am)return am<s.am;
return ap<s.ap;
}
};
__int64 calc(__int64 a){
__int64 a2=a*a,ans=-1,t,ap=a+1,am=a-1;
S s;
s.am=a-1;
s.ap=a+1;
std::set<S> memo;
while(memo.find(s)==memo.end()){
memo.insert(s);
t=(s.am+s.ap)%a2;
if(t>ans){
ans=t;
}
s.am=(s.am*am)%a2;
s.ap=(s.ap*ap)%a2;
//std::cout<<t<<" "<<s.am<<" "<<s.ap<<"\n";
}
return ans;
}
int main(){
__int64 ans=0,t;
for(int i=3;i<1001;i++){
t=calc(i);
std::cout<<i<<" "<<t<<"\n";
ans+=t;
}
std::cout<<ans<<"\n";
}
