プロジェクトオイラー問189 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20189
三角形の色塗り問題。
何も考えない漸化式で解です。

思考時間５分
コード記述時間１０分
計算時間１秒

#include<stdio.h>
#include<map>
#include<iostream>
std::map<int,__int64> dp[16];
//一行右から2bitずつ、00が赤、01が青、10が緑
 
void oddRow(int p,int lp,int r,int no,int no2,__int64 perm){
	if(p==lp){
		dp[r][no2]+=perm;
	}else{
		int c=(no>>(p*2))&3;
		if(c!=0)oddRow(p+1,lp,r,no,no2,perm);
		if(c!=1)oddRow(p+1,lp,r,no,no2+(1<<(2*p)),perm);
		if(c!=2)oddRow(p+1,lp,r,no,no2+(2<<(2*p)),perm);
	}
}

void evenRow(int p,int lp,int r,int no,int no2,__int64 perm){
	if(p==lp){
		dp[r][no2]+=perm;
	}else{
		bool ok[3]={true,true,true};
		if(p>0){
			int c=(no>>((p-1)*2))&3;
			ok[c]=false;
		}
		if(p<lp-1){
			int c=(no>>(p*2))&3;
			ok[c]=false;
		}
		if(ok[0])evenRow(p+1,lp,r,no,no2,perm);
		if(ok[1])evenRow(p+1,lp,r,no,no2+(1<<(2*p)),perm);
		if(ok[2])evenRow(p+1,lp,r,no,no2+(2<<(2*p)),perm);
	}
}


int main(){
	dp[0][0]=1;
	dp[0][1]=1;
	dp[0][2]=1;
	int even=2;
	int odd=1;
	std::map<int,__int64>::iterator it;
	for(int i=1;i<15;i++){
		for(it=dp[i-1].begin();it!=dp[i-1].end();it++){
			if(i%2==0){
				evenRow(0,even,i,(*it).first,0,(*it).second);		
			}else{
				oddRow(0,odd,i,(*it).first,0,(*it).second);
			}
		}
		if(i%2==0)even++;
		if(i%2==1)odd++;
	}
	__int64 ans=0;
	for(it=dp[14].begin();it!=dp[14].end();it++){
		ans+=(*it).second;
	}
	std::cout<<ans<<"\n";
}