「aoj2352挑戦中コード２」の編集履歴（バックアップ）一覧に戻る

aoj2352挑戦中コード２ - (2012/04/08 (日) 16:30:13) のソース

[[aoj2352挑戦中コード]]の続き。

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



#include<stdio.h>
#include <bitset>
#include <map>
#include <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]]