オイラープロジェクト161～170 - c21coterie @ ウィキ

問い161

http://projecteuler.net/problem=161
とりあえず速さより分かりやすさを重視して一段ずつ動的計画法というかメモ化というかそんな感じ。
途中までは３段ずつ注目し、最後の２段は最後の段を超えてピースをはめ込めないように注意すればそんなに難しくはなく、問題文を読んで３分で解法を思いついた♪。
うーんとりあえず素朴に求めたけどもっと賢い方法が幾らでもありそう。
問題１２０番超えたあたりから素朴な方法では解けず整数論の知識がいる問題が増えてきたようである。
そんな中こういう素朴に解ける問題を見つけると砂漠の中でオアシスを見つけたような気分になる。

#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>
const int w=9;
const int h=12;
struct S{
int row[3][w];
bool operator<(const S& s)const{
	for(int c=0;c<w;c++){
		if(row[0][c]!=s.row[0][c])return row[0][c]<s.row[0][c];
		if(row[1][c]!=s.row[1][c])return row[1][c]<s.row[1][c];
	}
	return false;
}
};
std::map<S,__int64> memo,next;
int pxs[][2]={	{0,1},
		{1,1},
		{0,1},
		{0,-1},
		{0,0},
		{1,2}};
int pys[][2]={	{1,0},
		{0,1},
		{1,1},
		{1,1},
		{1,2},
		{0,0}};
void saiki(S& s,int deep,__int64 perm,int row){
if(deep==w){
	S nextS;
	memset(nextS.row,0,sizeof(nextS.row));
	memcpy(nextS.row[0],s.row[1],sizeof(s.row[1]));
	memcpy(nextS.row[1],s.row[2],sizeof(s.row[2]));
	if(next.find(nextS)==next.end()){
		next[nextS]=perm;
	}else{
		next[nextS]+=perm;
	}
}else{
	if(s.row[0][deep]!=0){
		saiki(s,deep+1,perm,row);
	}else{
		int px1,px2,py1,py2;
		for(int i=0;i<6;i++){
			px1=deep+pxs[i][0];
			px2=deep+pxs[i][1];
			py1=pys[i][0];
			py2=pys[i][1];
			if(px1<0||w<=px1||px2<0||w<=px2)continue;
			if(py1<0||h<=py1+row||py2<0||h<=py2+row)continue;
			if(s.row[py1][px1]!=0||s.row[py2][px2]!=0)continue;
			s.row[py1][px1]=s.row[py2][px2]=1;
			saiki(s,deep+1,perm,row);
			s.row[py1][px1]=s.row[py2][px2]=0;
		}
	}
}
}
int main(){
std::map<S,__int64>::iterator it;
S s,ansS;
__int64 ans=0;
memset(ansS.row,0,sizeof(ansS.row));
memset(s.row,0,sizeof(s.row));
memo[s]=1;
for(int r=0;r<h;r++){
	for(it=memo.begin();it!=memo.end();it++){
		s=(*it).first;
		saiki(s,0,(*it).second,r);
	}
	memo.clear();
	memo.insert(next.begin(),next.end());
	next.clear();
	//if(r>=h-3){
		//ans+=memo[ansS];
		//std::cout<<ans<<" ";
	//	if(r==h-3)memset(ansS.row[1],0,sizeof(ansS.row[1]));
	//	if(r==h-2)memset(ansS.row[0],0,sizeof(ansS.row[0]));
	//}
}
std::cout<<memo[ansS];
}

問い162

http://projecteuler.net/problem=162
16進法では、数は以下の16個の数字によって表される
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
16進数の AF は、10進法での 10x16 + 15 = 175 と等しい。
3桁の16進数 10A, 1A0, A10, A01 には、0, 1, A の全てが現れている。
10進数で書くときと同様に、先頭の0は書かないことにする。
0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか?
16進数で答えよ。
(A,B,C,D,E,F は大文字とし、先頭や末尾の16進数であることを表す記号や先頭の0は許されない。つまり、1A3F ならOK。1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない。)

解法
2^63以内に答えが収まる問題ならそんなに怖くはない。
この問題も問題を読んでから５分で基本的な解法を思いつき、考えミスの修正に手間取って30分ほどでコードを書きあげた。
私にとって怖いのは整数論の知識が必要な数万桁とか数億桁を処理する問題などである。
何せ私が今までの人生で一番最後に受けた整数論関係の数学の授業といえばnCrとパスカルの三角形の授業をほんの少しの時間だけ。
きちんとした整数論の知識がいる問題になるとお手上げです。

#include<stdio.h>
#include<iostream>
bool spents[3]={false,false,false};
__int64 ans=0;//
void saiki(int deep,__int64 perm,bool isFirst){
if(deep==16&&spents[0]+spents[1]+spents[2]==3){
	ans+=perm;
}else if(deep==16&&spents[0]+spents[1]+spents[2]<3){
	return ;
}else{
	if(isFirst==true){
		//先頭0が続く場合
		saiki(deep+1,perm,true);
	}
	//0意外0が使われてないかまだ0か
	saiki(deep+1,perm*(16-((!spents[0])||isFirst)-!spents[1]-!spents[2]),false);//0,1,Aが使用済みなら以後は組み合わせに組み込む
	
	//この桁で初めて0か1かＡが設定される
	if(spents[0]==false&&isFirst==false){
		//0は先頭に来れない
		spents[0]=true;
		saiki(deep+1,perm,false);
		spents[0]=false;
	}
	if(spents[1]==false){
		spents[1]=true;
		saiki(deep+1,perm,false);
		spents[1]=false;
	}
	if(spents[2]==false){
		spents[2]=true;
		saiki(deep+1,perm,false);
		spents[2]=false;
	}
}
}
int main(){
saiki(0,1,true);
std::cout<<ans;
}

問い169

解法を思いつくまで5分、解法の細部を煮詰めるのに２０分もかかった問題。
解法が出来たらコードはあっという間にできた。

分解して整理すると01001+101110のような２進数同士の足し算２つに変換できる。
同じ桁には1が２つか1つか０個。
下の桁から足して繰り上り繰り上りなしのパタンを計算していけば簡単なメモ化計算で片が付きます。
Lispで書くと簡潔に記述できるな。

(defun calc (n a0 a1)
 (if (= n 0)
     a0
   (if (= (mod n 2) 0)
(calc (floor (/ n 2)) a0 (+ a0 a1))
     (calc (floor (/ n 2)) (+ a0 a1) a1))))
calc
(calc (expt 10 25) 1 0)

問い167

どの連続した3桁の和も9以下のような(９以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか?
とりあえずメモ化計算で片が付きましたが。
組み合わせの制限を使ってもう少し素早く答えを出す方法もありそうなきもします。

#include<stdio.h>
#include<string.h>
#include<iostream>
const int up=10;
__int64 memo[30][up][up];
int main(){
memset(memo,0,sizeof(memo));
//初めの３桁を設定
int t;
for(int i=100;i<1000;i++){
	t=i/100+(i/10)%10+i%10;
	if(t<up){
		memo[3][(i/10)%10][i%10]++;
	}
}
__int64 ans=0;
for(int i=4;i<21;i++){
	for(int j=0;j<up;j++){
		for(int k=0;k<up;k++){
			for(int l=0;l<up-j-k;l++){
				memo[i][k][l]+=memo[i-1][j][k];
				ans+=memo[i-1][j][k]*(i==20);
			}
		}
	}
	
}
std::cout<<ans<<"\n";
}