yukicoder : No.719 Coprime

今回色々ゴリ押している。
https://yukicoder.me/problems/no/719

問題

正整数Nが与えられる。
2～Nの整数集合のうち、２要素が互いに素となるような部分集合における全要素の和の最大値を求めよ。

解法

各素数を素因数に持つ値は1個しか部分集合に含めることはできないことを利用する。
以下を考えよう。
f(i,mask) := すでに(小さい順から)i番目以前の素数のうちmaskに相当する素数が利用済みの場合、i番目以降の素数の倍数による問題文に示す部分集合の最大値

上記をメモ化再帰で解く。
f(i,mask) = max(f(i+1,mask) , p+f(i+1,mask | g(p)))

maxの左側の項は、i番目の素数の倍数を使わないケースである。
右側の項のうち、pはi番目以前の素数のみを素因数に持ち、かつmaskに相当する素数を素因数に持たないものを総当たりしよう。
g(p)はpを素因数分解したときに登場する素因数の番号からなるbitmaskである。

ここで重要なのは、bitmaskは高々31に相当するもの、すなわち11番目の素数までだけ覚えておけばよい。
というのも、それ以降の素数、すなわち37以降の素数は2乗するとNを確実に超えるためbitmaskで覚えておく必要がないためである。

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;
int N;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int memo[1400][1<<12];
int dmask[1300];

int dfs(int id,int mask) {
	if(prime[id]>N) return 0;
	if(memo[id][mask]>=0) return memo[id][mask];
	memo[id][mask]=dfs(id+1,mask);
	for(int x=prime[id];x<=N;x+=prime[id]) {
		int y;
		for(y=id+1;prime[y]<=N;y++) if(x%prime[y]==0) break;
		if(prime[y]>N && (dmask[x]&mask)==0) memo[id][mask]=max(memo[id][mask], x+dfs(id+1,mask|dmask[x]));
	}
	return memo[id][mask];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cprime();
	MINUS(memo);
	for(i=2;i<=1270;i++) {
		FOR(j,20) if(prime[j]<32 && i%prime[j]==0) dmask[i] |= 1<<j;
	}
	
	cin>>N;
	cout<<dfs(0,0)<<endl;
	
}

まとめ

うーん、こういうのさっくり解けないなぁ。