「オイラープロジェクト110～120」の編集履歴（バックアップ）一覧に戻る
*問い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);
}
