TopCoder SRM 547 Div2 Hard RelativelyPrimeSubset

TopCoder グラフ理論 動的計画法

問題

n個の正の整数S[i]が与えられる。
この整数から、部分集合sを、sのどの二つの要素も互いに素であるように選びたい。


sの要素の数の最大値はいくつか、求めよ。

制約条件

S[i]≦100
S[i]は互いに異なる
n≦50

方針

Sの互いに素でない要素を辺で結んだグラフを考えると、
求めるのはこのグラフの最大独立集合。


なのだけど、最大独立集合をO(2^sqrt(2m) * n)で求めたらTLEだった。


Sの上限が小さいことを使う。
S[i]が50以上の素因数を持っていたら、
その素因数が公約数になることはないので、その素因数を無視してよい。


すると、素因数は2〜47の15個に限られるので、
dp[i][j]を、i番目の要素まで見て、今素因数をjで表される集合だけ使ったときの
要素の最大値として、これを更新していくようなDPをすればよい。

ソースコード

TLEしたやつ（O(2^sqrt(2m) n^2)）
計算量をO(2^sqrt(2m) * n)に落として、自明に採用できるノードを採用することにしたら通るような気がしなくもない。
後でやってみる。

int max_clique(vector<vi> &e){
	int n = e.size(), deg[50] = {};
	int m = 0;
	rep(i, n) rep(j, n) if(e[i][j]) deg[i]++, m++;
	m /= 2;
	int ans = -1;
	rep(i, n) if(deg[i] * deg[i] < 2 * m){
		int v[50], t = 0;
		rep(j, n) if(e[i][j]) v[t++] = j;
		
		rep(j, 1 << t){
			rep(k, t) rep(l, k)
			if((j & 1 << k) && (j & 1 << l) && !e[v[k]][v[l]])
				goto FAIL;
			ans = max(ans, __builtin_popcount(j) + 1);
			FAIL:;
		}
		vector<vi> nxt = e;
		nxt.erase(nxt.begin() + i);
		rep(j, n - 1) nxt[j].erase(nxt[j].begin() + i);
		ans = max(ans, max_clique(nxt));
		break;
	}
	
	if(ans < 0){
		rep(i, 1 << n){
			rep(j, n) rep(k, j)
			if((i & 1 << j) && (i & 1 << k) && !e[j][k])
				goto FAIL2;
			ans = max(ans, __builtin_popcount(i));
			FAIL2:;
		}
	}
	ans = max(ans, 1);
	return ans;
}

class RelativelyPrimeSubset {
	public:
	int findSize(vector <int> S) 
	{
		int n = S.size();
		vector<vi> e(n, vi(n));
		rep(i, n) rep(j, n) e[i][j] = i != j && __gcd(S[i], S[j]) == 1;
		
		return max_clique(e);
	}
};

計算量O(n^sqrt(2m) n)に落として、自明な頂点は必ず使うようにした版。
結局TLEだった。

vector<vi> e;
int n, m, deg[50];
bool use[50];

int max_clique(){
	int ans = -1;
	rep(i, n) if(use[i] && deg[i] * deg[i] < 2 * m){
		int v[50], t = 0;
		rep(j, n) if(use[j] && e[i][j]) v[t++] = j;
		vector<bool> ok(1 << t);
		ok[0] = 1;
		
		rep(j, 1 << t) if(j){
			int k = 0;
			for(; !(j & 1 << k); k++);
			if(!ok[j ^ 1 << k]) goto FAIL;
			rep(l, t) if(k != l && (j & 1 << l) && !e[v[k]][v[l]]) goto FAIL;
			
			ans = max(ans, __builtin_popcount(j) + 1);
			ok[j] = 1;
			FAIL:;
		}
		
		use[i] = 0;
		rep(j, t) deg[v[j]]--, m--;
		
		ans = max(ans, max_clique());
		break;
	}
	
	if(ans < 0){
		int v[50], t = 0;
		rep(i, n) if(use[i]) v[t++] = i;
		vector<bool> ok(1 << t);
		ok[0] = 1;
		
		rep(i, 1 << t) if(i){
			int k = 0;
			for(; !(i & 1 << k); k++);
			if(!ok[i ^ 1 << k]) goto FAIL2;
			rep(j, t) if(j != k && (i & 1 << j) && !e[v[j]][v[k]]) goto FAIL2;
			ans = max(ans, __builtin_popcount(i));
			FAIL2:;
		}
		
		if(t) ans = max(ans, 1);
		else ans = max(ans, 0);
	}
	return ans;
}

class RelativelyPrimeSubset {
	public:
	int findSize(vector <int> S) 
	{
		int ans = 0;
		rep(i, S.size()){
			bool ok = 1;
			rep(j, S.size()) if(i != j && __gcd(S[i], S[j]) != 1) ok = 0;
			if(ok){
				ans++;
				S.erase(S.begin() + i--);
			}
		}
		n = S.size();
		m = 0;
		e = vector<vi>(n, vi(n));
		rep(i, n) deg[i] = 0, use[i] = 1;
		rep(i, n) rep(j, i) if(__gcd(S[i], S[j]) == 1){
			e[i][j] = e[j][i] = 1;
			m++;
			deg[i]++; deg[j]++;
		}
		ans += max_clique();
		
		return ans;
	}
};