aoj2352挑戦中コード２ - c21coterie @ ウィキ

aoj2352挑戦中コードの続き。

正答者のタイムにバラツキがない以上貪欲法で片が付いているのかな？
どう考えてもNP困難な問題に思えて高速化テクニックでごまかそうとしているのだが中々タイムが縮まらない。
std::bitsetが遅すぎるだけなのだろうか？

<stdio.h>

<bitset>

<map>

<string>

std::bitset<102> maskA;

class bitSetSorter {

public:
  	bool operator()( const std::bitset<102> &L, const std::bitset<102> &R ) const
  	{
	//return L.to_string()>R.to_string();
	unsigned long Ls,Rs;
	Ls=(L>>96).to_ulong();
	Rs=(R>>96).to_ulong();
	
	if(Ls!=Rs)return Ls>Rs;

	Ls=((L>>64)&maskA).to_ulong();
	Rs=((R>>64)&maskA).to_ulong();
	
	if(Ls!=Rs)return Ls>Rs;

	Ls=((L>>32)&maskA).to_ulong();
	Rs=((R>>32)&maskA).to_ulong();
	
	if(Ls!=Rs)return Ls>Rs;
	
	Ls=(L&maskA).to_ulong();
	Rs=(R&maskA).to_ulong();
	if(Ls!=Rs)return Ls>Rs;
	return false;
}

};

void putAns(const std::bitset<102>& ans,int n){

int c=0;
for(int i=n-1;i>=0;i--){
	if(ans.test(i)==1){
		printf("%s%d",c==0?"":" ",n-i);
		c=1;
	}
}
printf("\n");

}

int main(){

int n,xs[102];
std::bitset<102> cons[102],nowSet,nowOut,temp,ans,ansOut,mask;
std::map<std::bitset<102>,std::bitset<102>,bitSetSorter> memos[102];//ここをコメントアウトはずすとエラー
std::map<std::bitset<102>,std::bitset<102>,bitSetSorter>::iterator it;

nowSet.reset();
nowOut.reset();
ans.reset();
mask.reset();
mask.flip();

maskA.reset();
for(int i=0;i<32;i++)maskA.set(i);

scanf("%d",&n);
for(int i=n-1;i>=0;i--){
	scanf("%d",&xs[i]);
	cons[i].reset();
	cons[i].set(i);
	for(int j=n-1;j>i;j--){
		if(xs[j]%xs[i]==0||xs[i]%xs[j]==0){
			cons[i].set(j);
			cons[j].set(i);
		}
	}
}
for(int i=0;i<n;i++){
	for(int j=i+1;j<n;j++){
		if((cons[i]&cons[j])==cons[j]){
			cons[i].reset();
			break;
		}
	}
	if(cons[i].count()==1){
		nowSet.set(i);
		cons[i].reset();
		continue;
	}
}




memos[n][nowSet]=nowSet;
ans=nowSet;
ansOut=nowSet;

for(int i=n-1;i>=0;i--){
	mask.reset(i);
	if(cons[i].any()==false){
		memos[i].insert(memos[i+1].begin(),memos[i+1].end());
		continue;
	}
	
	for(it=memos[i+1].begin();it!=memos[i+1].end();it++){
		nowOut=(*it).first;
		nowSet=(*it).second;
		nowOut=nowOut&mask;
		temp=cons[i]&mask;
		//次の数字を答えの集合に組み込める場合
		if((temp|nowOut)!=nowOut){
			if(memos[i].find(nowOut)==memos[i].end()){
				memos[i][nowOut]=nowSet;
			}else{
				temp=memos[i][nowOut];
				if(temp.count()<nowSet.count()){
					memos[i][nowOut]=nowSet;
				}else if(temp.count()==nowSet.count()&&temp.to_string()<nowSet.to_string()){
					memos[i][nowOut]=nowSet;
				}
			}
		}
		
		//次の数字を組み込めるかのチェック
		if(nowOut.test(i)==0&&(cons[i]&nowSet).any()==false){
			nowOut|=cons[i];
			nowSet.set(i);
		}else{
			continue;
		}
		//答えのサブセットで答えより悪い場合枝かり
		if((ansOut|nowOut)==nowOut&&nowSet.count()<=ans.count()){
			continue;
		}
		nowOut&=mask;
		
		if(memos[i].find(nowOut)==memos[i].end()){
			memos[i][nowOut]=nowSet;
		}else{
			temp=memos[i][nowOut];
			if(temp.count()<nowSet.count()){
				memos[i][nowOut]=nowSet;
			}else if(temp.count()==nowSet.count()&&temp.to_string()<nowSet.to_string()){
				memos[i][nowOut]=nowSet;
			}
		}
		if(ans.count()<nowSet.count()){
			ans=nowSet;
			ansOut=nowOut;
		}else if(ans.count()==nowSet.count() && ans.to_string()<nowSet.to_string()){
			ans=nowSet;
			ansOut=nowOut;
		}
	}
	printf("(%d %d)\n",i,memos[i].size());
}
 putAns(ans,n);

}

ファンタジー系ゲーム用アイテムアイディアリスト1