「オイラープロジェクト110～120」の編集履歴（バックアップ）一覧に戻る

オイラープロジェクト110～120 - (2012/08/29 (水) 10:16:41) のソース

*問い114
最初動的計画法で解こうと適当に書いてみるもプログラムのミスか少し取りこぼす数が出たので、まずは数字の変化を眺めようと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";
	}
 }




*問い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;
 }