TopCoder SRM 547 Div2 Hard RelativelyPrimeSubset

どんどんDiv2 Hardをさかのぼってみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12074

問題

1～100のうちdistinctないくつかの数値で構成される集合がある。
ここから、任意の要素ペアを作った場合に互いに素であるような最大に部分集合のサイズを答えよ。

解法

まず各数値を素因数分解し、2～97の各素数を素因数に持つかどうかでbitmapとして表現してsetに放り込む。
なお、以下の数値はsetに放り込まなくても無条件で目的の部分集合に含まれると考えてよい。

• 1はどの自然数についても互いに疎になるので、1は部分集合に含められる。
• 53以上の素数を素因数に持つ100以下の合成数はないので、53以上の素数は部分集合に求められる。

後は、set中でbitmapが重ならないようにできるだけ多くの項目を選択すればよい。
マッチングとかフローとか使わなくても何とか間に合う。

int pr[51][51];

int NP,prime[100];
const int prime_max = 100;
void cprime() {
	static int p[prime_max];
	int i,j;
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[NP++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=i;
	}
}

class RelativelyPrimeSubset {
	set<int> M2;
	map<int,int> memo;
	public:
	int dpdp(int mask,int lb) {
		int i,r=0,ma=0;
		if(memo.find(mask)!=memo.end()) return memo[mask];
		ITR(it,M2) {
			if(mask & *it) continue;
			int lb2 = *it & (-*it);
			if(lb2<lb) continue;
			ma = max(ma,1+dpdp(mask | *it, lb2));
		}
		return memo[mask]=ma;
		
	}
	
	int findSize(vector <int> S) {
		int i,x,y,m,L=S.size(),has1=0;
		NP=0;
		cprime();
		
		set<int> M;
		FOR(i,L) {
			int ma=0;
			FOR(x,NP) if(S[i]%prime[x]==0) ma |= 1<<x;
			if(S[i]==1) has1=1;
			if(ma) M.insert(ma);
		}
		M2.clear();
		memo.clear();
		ITR(it,M) {
			x=0;
			if(__builtin_popcount(*it)==1 && *it>=1<<15) {
				has1++;
				continue;
			}
			ITR(it2,M2) if((*it2 | *it) == *it) x++;
			if(x==0) M2.insert(*it);
		}
		return dpdp(0,0) + has1;
	}
};

まとめ

「２部グラフじゃないし最大独立集合をどうやって求めるか…」と迷ったけど、普通にDFSで解けた。