Codeforces #213 Div1. C. Beautiful Set

Bで無駄な時間を使わず、先にCに行けばよかった…。
これは本番後ノーヒントで解けた。
http://codeforces.com/contest/364/problem/C

問題

整数K(10<=K<=5000)が与えられる。
以下の条件を満たす数列を１つ答えよ。

• K要素のdistinctな整数列であり、各要素は1～(2*K*K)の範囲にある。
• ある要素が素数pで割り切れる場合、整数列中K/2個以上は同じpで割り切れなければならない。

解法

いろんな素数を使ってしまうと、その素数を素因数に含む数値をK/2個以上準備しないといけないため掛け合わせでどんどん数値が大きくなってしまう。
小さい素数をうまく使うことで処理すればよい。

たとえば素数を下から3つ(2,3,5)使うとする。
この場合、2*3*5=30に対し、2,3,5を掛けて得られる数を多数生成して答えの数列に追加すれば、これらは2,3,5いずれでも割れる。
これらで足りないなら、(2,3)(2,5)(3,5)のそれぞれの素数対を素因数に持つものを同様に追加していく。
それでも足りなければ、2,3,5の累乗を追加していく。

上記の手順でK個の数値を生成でき、かつ実際に各素数の約数となるものがK/2を超えていればそれは答えとなる。

実際はKの値によっては素数が2つ(2,3)で十分だったり、もっとたくさん(2,3,5,7,11)必要だったりする。
これらは使う素数を少ないところから初めて、どんどん多くしていけばよい。
実行時間は意外と問題ない。

以下の解答では、先に使う素数をbitmaskで表し、それらの倍数で表現できる数をsetに突っ込んでいる。

int K;
int R[5001];
set<int> S[64];
int pr[]={2,3,5,7,11,13};

int check(int id) {
	int i,x,y;
	int num[6],rn;
	int snum[64];
	vector<int> mask[7];
	vector<int> S2[64];
	
	for(x=1;x<1<<id;x++) mask[__builtin_popcount(x)].push_back(x);
	
	FOR(i,64) snum[i]=S[i].size();
	ZERO(snum);
	rn=0;
	for(i=id;i>=0&&rn<K;i--) {
		while(1) {
			y=rn;
			FOR(x,mask[i].size()) {
				if(snum[mask[i][x]]>=S[mask[i][x]].size()) goto out;
				if(rn==K) goto out;
				snum[mask[i][x]]++;
				rn++;
			}
			if(y==rn) break;
		}
		out:
		;
	}
	for(i=id;i>=0&&rn<K;i--) {
		FOR(x,mask[i].size()) {
			y=min(K-rn,(int)S[mask[i][x]].size()-snum[mask[i][x]]);
			rn+=y;
			snum[mask[i][x]]+=y;
		}
	}
	if(rn<K) return 0;
	ZERO(num);
	FOR(i,1<<id) FOR(x,id) if(i&(1<<x)) num[x]+=snum[i];
	FOR(x,id) if(num[x]<K/2) return 0;
	
	FOR(i,1<<id) {
		ITR(it,S[i]) {
			if(snum[i]--==0) break;
			_P("%d ",*it);
		}
	}
	_P("\n");
	return 1;
}

set<int> lup(int id) {
	int i,x;
	set<int> s1,s2,s3;
	
	x=1;
	FOR(i,6) if(id&(1<<i)) x*=pr[i];
	if(x>2*K*K) return s1;
	s1.insert(x);
	s2.insert(x);
	while(!s2.empty()) {
		s3.clear();
		FOR(i,6) if(id&(1<<i)) ITR(it,s2) {
			if(*it*pr[i]<=2*K*K) {
				s1.insert(*it*pr[i]);
				s3.insert(*it*pr[i]);
			}
		}
		s2=s3;
	}
	return s1;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>K;
	for(x=1;x<=63;x++) S[x]=lup(x);
	for(i=1;i<=6;i++) if(check(i)) break;
}

まとめ

BよりC行けばよかった。