「aoj2352挑戦中コード２」の編集履歴（バックアップ）一覧はこちら

「aoj2352挑戦中コード２」(2012/04/08 (日) 16:30:13) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

 #include<stdio.h>
 #include <bitset>
 #include <map>
 std::bitset<102> mask;
 class bitSetSorter {
	public:
   	bool operator()( const std::bitset<102> &L, const std::bitset<102> &R ) const
   	{
		return hikaku(L,R);
	}
	bool hikaku( const std::bitset<102> &L, const std::bitset<102> &R )const{
	if((L>>96).to_ulong() < (R>>96).to_ulong())return false;
   	else if((L>>96).to_ulong() > (R>>96).to_ulong())return true;
	if(((L>>64)&mask).to_ulong() < ((R>>64)&mask).to_ulong())return false;
	else if(((L>>64)&mask).to_ulong() > ((R>>64)&mask).to_ulong())return true;
	if(((L>>32)&mask).to_ulong() < ((R>>32)&mask).to_ulong())return false;
   	else if(((L>>32)&mask).to_ulong() > ((R>>32)&mask).to_ulong())return true;
	if((L&mask).to_ulong() < (R&mask).to_ulong())return false;
   	else if((L&mask).to_ulong() > (R&mask).to_ulong())return true;
	return false;
	}
 };
 int main(){
	int n,xs[102];
	std::bitset<102> cons[102],nowSet,nowOut,temp,ans;
	printf("ok2");
	//std::map<std::bitset<102>,std::bitset<102>,bitSetSorter> memo,next;//ここをコメントアウトはずすとエラー
 }

コメント部分を外したときのエラーコード
C:\Users\HORIE~1.OWN\AppData\Local\Temp\ccQDBYsK.o:aoj2352-8.cpp:(.text$_ZN9__gnu_cxx13new_allocatorISt13_Rb_tree_nodeISt4pai
rIKSt6bitsetILj102EES4_EEE10deallocateEPS7_j[__gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<std::bitset<102u> const, s
td::bitset<102u> > > >::deallocate(std::_Rb_tree_node<std::pair<std::bitset<102u> const, std::bitset<102u> > >*, unsigned int
)]+0xd): undefined reference to `operator delete(void*)'
C:\Users\HORIE~1.OWN\AppData\Local\Temp\ccQDBYsK.o:aoj2352-8.cpp:(.eh_frame+0x13): undefined reference to `__gxx_personality_
v0'
C:\Users\HORIE~1.OWN\AppData\Local\Temp\ccQDBYsK.o:aoj2352-8.cpp:(.eh_frame$_ZNSt8_Rb_treeISt6bitsetILj102EESt4pairIKS1_S1_ES
t10_Select1stIS4_E12bitSetSorterSaIS4_EED1Ev+0x13): undefined reference to `__gxx_personality_v0'
collect2: ld returned 1 exit status












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

[[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]]