「プロジェクトオイラー問い111～120」の編集履歴（バックアップ）一覧に戻る
*Problem 112 「はずみ数の濃度について調べ上げよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20112
左から右までどの桁もその左の桁を上回らない数を増加数と呼ぶ. 例えば, 134468.
同様に, どの桁もその右の桁を上回らない数を減少数と呼ぶ. 例えば, 66420.
増加数でも減少数でもない正の整数を「活発な」数と呼ぶことにする. 例えば, 155349.
100以下の数に活発な数が無いのは明らかだが, 1000より下の数では半数を少し上回る数(525)が活発である.
実際, 活発な数の割合が50%に達する最少の数は538である.
驚くべきことに, 活発な数はますます一般的になり, 21780では活発な数の割合は90%に達する.
活発な数が数の割合が99%ちょうどになる最小の数を求めよ.
解法
一つずつ調べて超えるかをチェックするだけで十分速度は出ます。
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
bool check(int n){
int u=0,d=0,count=0,num=n;
int k=n%10,k2;
n/=10;
while(n!=0){
k2=n%10;
if(k<=k2)u++;
if(k>=k2)d++;
count++;
k=k2;
n/=10;
}
return u!=count&&d!=count;
}
int main(){
int n=100;
int count=0;
srand(time(NULL));
while(1){
count+=check(n);
if((n-count)*100==n)break;
n++;
}
printf("%d",n);
}
*Problem 113 「googol数未満ではずみ数でないものはいくつあるか?」 †
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 10＾10未満では277032個しかない.
googol数 (10＾100) 未満ではずみ数でないものの数を答えよ.
解法
増加数と減少数の両方を一ケタずつ別々に計算して最後に足し合わせます。
メモ化計算で一発です。
増加数でありかつ減少数である数が２度足されているので最後にそれを引くくらいです。
計算量は数万回程度ですが他のかたの回答を見るとnCrを使ったもっとカッコいいコードで解いてるようです。
#include<stdio.h>
#include<iostream>
#include<string.h>
int main(){
__int64 memoUp[101][10];
__int64 memoDown[101][10],sum=0;
__int64 ans=0;
int keta=100;
memset(memoUp,0,sizeof(memoUp));
memset(memoDown,0,sizeof(memoDown));
for(int i=0;i<10;i++)memoUp[0][i]=memoDown[0][(i==0)+i]=1;
for(int i=0;i<keta-1;i++){
for(int j=0;j<10;j++){
for(int k=j;k<10;k++){
memoUp[i+1][k]+=memoUp[i][j];
memoDown[i+1][j]+=memoDown[i][k];
}
}
for(int j=1;j<10;j++)sum+=memoDown[i][j]+memoUp[i][j];
}
for(int i=1;i<10;i++){
ans+=memoUp[keta-1][i]+memoDown[keta-1][i];
}
std::cout<<ans+sum-keta*9;
}
*Problem 114 「少なくとも3ユニットの長さを持つブロックを離して一列に敷き詰める方法の数を調べ上げよ」
*Problem 115 「ブロックを離して1列に敷き詰める方法の数の一般化式を求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20114
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20115
解法
メモ化計算で済みますが少しコードに穴があります。
最後で帳尻合わせてますが少し考えが足らないコードのようです。
#include<stdio.h>
#include<iostream>
#include<vector>
__int64 calc(int m,int n){
__int64 add,ans=0;
std::vector<__int64> count;
for(int i=0;i<=n+2;i++)count.push_back(0);
for(int i=1;i<=n-m+1;i++)count[i]=1;
for(int i=1;i<=n-m+1;i++){
add=0;
for(int j=i+m+1;j<=n+2;j++){
add+=count[i];
if(j>n)add=count[i];
count[j]+=add;
}
}
for(int i=n;i<=n+2;i++)ans+=count[i];
return ans+1;//全部黒の場合を足す
}
int main(){
std::cout<<"問い114の答え"<<calc(3,50);
int n=51;
__int64 re;
while(1){
re=calc(50,n);
if(re>1000*1000)break;
n++;
}
std::cout<<"\n問い115の答え"<<n;
}
*Problem 116 「正方形のタイルを3つの色タイルのうち一つに置き換える方法の数を調べ上げよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20116
一列に並んだブロックを長さの決まったピースで置き換える問題。
解法
メモ化で一発です。
#include<stdio.h>
#include<iostream>
__int64 calc(int n){
__int64 count[52]={0};
for(int i=1;i<=50-n+1;i++)count[i]=1;
for(int i=1;i<50;i++){
for(int j=i+n;j<=51;j++)count[j]+=count[i];
}
return count[51];
}
int main(){
std::cout<<calc(2)+calc(3)+calc(4);
}
*Problem 117 「異なるサイズのタイルを使って一列にタイルを敷く方法の数を調べ上げよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20117
解法
メモ化で一発でしたが、なんか他の人のコードを見てますとf(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)で決まるらしいです。
２重ループより一重ループの方がそらいいよな、勉強になる。
#include<stdio.h>
#include<iostream>
__int64 calc(){
__int64 count[52]={0},add;
for(int i=1;i<=49;i++)count[i]=1;
for(int i=1;i<50;i++){
add=count[i];
for(int j=i+2;j<=51;j++){
count[j]+=add;
if(j<=i+3)add+=count[i];
}
}
return count[51]+1;
}
int main(){
std::cout<<calc();
}
*Problem 118 「素数を要素として作られる集合の場合の数を探し当てよ」 †
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り, 複数の集合を作ることができる. 集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.
1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?
解法
再帰による全探索でも十分速度が出ます。
素数の判定を毎回しているのがもったいないくらいですが探索範囲が狭いので気にしません。
#include<stdio.h>
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool spents[10]={true};
void saiki(int num,int old,int deep){
if(deep==0)for(int i=1;i<10;i++)spents[i]=false;
if(deep==9){
ans+=num>old&&isPrime(num);
}else{
bool ok=num>old&&isPrime(num);
for(int i=1;i<10;i++){
if(spents[i]==false){
spents[i]=true;
saiki(num*10+i,old,deep+1);
if(ok==true)saiki(i,num,deep+1);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
printf("%d",ans);
}
*Problem 120 「(a-1)^n+(a+1)^n を a^2 で割ったとき最大となる余りを求めよ」 †
(a-1)＾n+(a+1)＾n を a＾2 で割った余りを r と定義する.
例えば, a=7, n=3 の時, r=42 である: 63 + 83 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる.
3 ≤ a ≤ 1000 において, Σ rmax を求めよ.
解法
地道にmodで割りながら周回したら計算終了としました。
多分数式変形から入らないと駄目だなこれ。
このコードはとりあえず解いているだけで何の賢さもありません。
#include<stdio.h>
#include<set>
#include<iostream>
struct S{
int n,m;
bool operator<(const S& s)const{
if(n!=s.n)return n<s.n;
return m<s.m;
}
};
int calc(int a){
S s;
s.n=a-1;
s.m=a+1;
int ans=0,a2=a*a,t;
std::set<S> memo;
while(memo.find(s)==memo.end()){
memo.insert(s);
t=(s.n+s.m)%a2;
if(t>ans)ans=t;
s.n=(s.n*(a-1))%a2;
s.m=(s.m*(a+1))%a2;
}
return ans;
}
int main(){
__int64 ans=0;
for(int a=3;a<=1000;a++)ans+=calc(a);
std::cout<<ans;
}
