AtCoder ARC #141 : D - Non-divisible Set

この解法賢いな…。
https://atcoder.jp/contests/arc141/tasks/arc141_d

問題

1～2Mの集合Sが与えられる。
Sの部分集合のうち、2要素のうち片方が片方の倍数であるような関係にない、M要素の集合を作りたい。

Sの各要素に対し、その要素を部分集合に含み、かつ条件を満たす集合を作れるか判定せよ。

解法

1～2Mの中からM要素選ぶので、奇数pに対しp*(2^n)の形をとる数値は、Sの部分集合に1個ずつ入らなければならない。
また、p'がpの倍数である場合、p*(2^n)とp'*(2^n')を両方Sに加えるためには、n＞n'でなければならない。
この条件より、以下の2つを考えると各pに対し取りえるnの範囲がわかる。

• pの小さい順に、nを極力大きい値を取るように埋めた場合
• pの大きい順に、nを極力小さい値を取るように埋めた場合

あとはSの各要素に対し、それらが上記範囲に入るか判定していく。

int N,M;
int A[666666];
int C[666666];
set<int> P[606060];
int L[606060],R[606060];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		C[A[i]]++;
		x=A[i];
		y=0;
		while(x%2==0) {
			x/=2;
			y++;
		}
		P[x].insert(y);
	}
	
	for(i=1;i<=2*M;i+=2) R[i]=100;
	int ng=0;
	for(i=1;i<=2*M;i+=2) {
		auto it=P[i].lower_bound(R[i]);
		if(it==P[i].begin()) {
			ng=1;
			break;
		}
		R[i]=*prev(it);
		for(j=i*2;j<=2*M;j+=i) if(j%2) R[j]=min(R[j],R[i]);
	}
	for(i=2*M-1;i>=1;i-=2) {
		L[i]=-1;
		for(j=i*2;j<=2*M;j+=i) if(j%2) L[i]=max(L[j],L[i]);
		auto it=P[i].lower_bound(L[i]+1);
		if(it==P[i].end()) {
			ng=1;
			break;
		}
		L[i]=*it;
	}
	
	FOR(i,N) {
		if(ng) {
			cout<<"No"<<endl;
		}
		else {
			x=A[i];
			y=0;
			while(x%2==0) {
				x/=2;
				y++;
			}
			if(L[x]<=y&&y<=R[x]) {
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
			
		}
	}
	
	
}

まとめ

2M個からM個選ぶのに、p*(2^n)に着目することに思いが至らなかった…。