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

https://projecteuler.net/problem=300
Protein folding
Problem 300「タンパク質の畳込み」 †

タンパク質の折り畳みを簡素化した問題。
こんなトイプロブレム（玩具の問題）が解けても現実の問題を解けるわけでもなし。
世間から見たらきっと凄くレベルの低いところを勉強してんだろうな俺。

２日間かけて記述。
色々工夫した結果計算時間１６分まで短縮。
遅い、、、競技プログラムの世界で見ても底辺が書くコードに分類されるな俺。

２次元タンパク質の折りたたみ方全体を木に縮約して計算量を落としてみた。
もっとも原始的な発想は　PとHの全パターン*全折り畳み　で検証することである、これでもそこそこの速度は出る。

ここで工夫すべきは、あるpとｈのパターンを代入した時全折り畳みを高速に検証できる関数を書けるならそれは良い手法である。
そのために全折り畳みを一つの木に縮約して、あるphの組での検証を高速化した。

所で最大の接触点数を評価するとき
HHHHHHHP
HHHHHHHH
は７文字目まで同じ評価になります。
つまりは無駄な評価を何度もしてることになります。
この無駄を省きます。

その結果計算時間１０分になりました。

残念ながらここから先が見えません。

私寝たきり老人状態だったので中学校教育は受けてません。
そんな人間の浅知恵です。

#include<stdio.h>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<math.h>


const int LIMIT=15;

struct E{
	int x,y;
	bool operator<(const E& e1)const{
 		if(x!=e1.x)return x<e1.x;
		return y<e1.y;
	}
	bool isCon(E& e1){
		if(e1.x+1==x&&e1.y==y)return true;
		if(e1.x-1==x&&e1.y==y)return true;
		if(e1.x==x&&e1.y+1==y)return true;
		if(e1.x==x&&e1.y-1==y)return true;
		return false;
	}
};

std::vector<int> conVec;
std::vector<E> vecEs;
std::set<E> sets;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
__int64 count=0;

std::map<__int64,__int64> tree0,tree1;


void to_tree(__int64 p,__int64 no){
	if(p==conVec.size()){
		return ;
	}else{
		__int64 next=tree0.size()+tree1.size()+1;
		if(conVec[p]==1){
			if(tree1.find(no)==tree1.end()){
 				tree1[no]=next;
			}
			to_tree(p+1,tree1[no]);
		}else{
		if(tree0.find(no)==tree0.end()){
			tree0[no]=next;
			}
			to_tree(p+1,tree0[no]);
		}
	}
}

void saiki(E e1){
	vecEs.push_back(e1);
	int size=vecEs.size();
	sets.insert(e1);
	E e2;
	for(int i=size-2;i>=0;i-=2){
		e2=vecEs[i];
		if(e1.isCon(e2)==true){
			conVec.push_back(1);
		}else{
			conVec.push_back(0);
		}
	}
	
	if(vecEs.size()==LIMIT){
		
		to_tree(0,0);
	}else{
		for(int i=0;i<4;i++){
			e2.x=e1.x+dx[i];
			e2.y=e1.y+dy[i];
			if(sets.find(e2)==sets.end()){
				saiki(e2);
			}
		}	
	}
	
	for(int i=size-2;i>=0;i-=2){
		conVec.pop_back();
	}
	vecEs.pop_back();
	sets.erase(e1);
}

std::map<int,int> memo;
void tree_search(int p,int phNo,int no,int c1){
	if(p==conVec.size()){
		if(memo.find(phNo)==memo.end())memo[phNo]=c1;
		else memo[phNo]=std::max(memo[phNo],c1);
	}else{
		if((tree1.find(no)!=tree1.end())){
			//std::cout<<"a"<<no<<" ";
			tree_search(p+1,phNo,tree1[no],c1+conVec[p]);
 		}
 		if(tree0.find(no)!=tree0.end()){
			//std::cout<<"b"<<no<<" ";
			tree_search(p+1,phNo,tree0[no],c1);
		}
	}
	
}

void saiki2(int p,int no){
	if(p==LIMIT){
		count++;
		if(count%100==0)std::cout<<"\n"<<no<<" "<<count<<" ";
		tree_search(0,no,0,0);
	}else{
		
		for(int i=p-1;i>=0;i-=2){
			int no2=no;
			if(((no2>>i)&1)==1){
				conVec.push_back(1);
			}else{
				conVec.push_back(0);
			}
		}
		saiki2(p+1,no+(1<<p));
		int dell=0;
		for(int i=p-1;i>=0;i-=2){
			conVec[conVec.size()-1-dell]=0;
			dell++;
		}
		saiki2(p+1,no);
		for(int i=p-1;i>=0;i-=2){
			conVec.pop_back();
		}
	}
} 


int main(){
	E e1;
	e1.x=0;
	e1.y=0;
	vecEs.push_back(e1);
	sets.insert(e1);
	e1.x=0;
 	e1.y=1;
	saiki(e1);
	saiki2(0,0);
	std::map<int,int>::iterator it;
	int ans=0;
	for(it=memo.begin();it!=memo.end();it++){
 		ans+=(*it).second;
		//std::cout<<(*it).first<<" "<<(*it).second;
	}
	printf("\nans=%d/%lf\n",ans,pow(2,LIMIT));
}