※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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



#include plugin Error : 指定されたページはございません。
<stdio.h>
#include plugin Error : 指定されたページはございません。
<bitset>
#include plugin Error : 指定されたページはございません。
<map>
#include plugin Error : 指定されたページはございません。
<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);
}