kmjp's blog

競技プログラミング参加記です

Codeforces #412 Div1 C. Prairie Partition

本番手こずったけど何とか解けた。
http://codeforces.com/contest/806/problem/C

問題

数値Xのprairie partitionとは、X=1+2+4+...+2^(k-1)+r、となるk,r(0≦r≦2^k)であらわしたものとする。
今いくつかの整数をそれぞれprairie partitionで表現したとき、登場する整数群が入力で与えられる。

そのような整数群を生成するのはもともといくつ整数があった場合か。
可能な範囲で列挙せよ。

解法

元の整数の数を総当たりしよう。

元の整数の数Pが決まっているとする。
Xを選ぶ場合、できるだけkが大きい方が、最後rのとれる値の範囲が広がってよい。
よって、まずは前処理として元の整数群中に2の累乗がいくつあるかを求めておき、またあるkが何個とれるか大きい順に求めておこう。

Pに対し、とれるkのうち上位P個を選んだ場合、まず元の整数群から対応する2の累乗を取り除いたと考えて、さらにP個の整数に対するr≦2^kの範囲の整数を取り除けばすべてを取り除けるかを判定すればよい。
余った整数のうち、ある2の累乗以下の値が何個あるかを考えていけば、各Pに対しlog(X)で条件を満たすか判定できる。

int N;
ll A[101010];
int num[45];
int les[45];
int start[45];
int lessum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		j=0;
		while(1LL<<(j+1)<=A[i]) j++;
		if(A[i]&(A[i]-1)) les[j]++;
		else num[j]++;
	}
	
	vector<int> V;
	int start_sum=0;
	for(i=40;i>=0;i--) {
		int mi=num[i];
		FOR(j,i+1) mi=min(mi,num[j]);
		FOR(j,mi) V.push_back(i);
		start[i]=mi;
		FOR(j,i+1) num[j]-=mi;
		if(j) les[j-1]+=num[j];
	}
	
	vector<int> R;
	for(i=V.size();i>=1;i--) {
		int can=0,lef=0;
		for(j=0;j<=40;j++) {
			lef+=les[j];
			lef-=min(lef,start[j]);
		}
		if(lef==0) R.push_back(i);
		x=V[i-1];
		start[x]--;
		FOR(j,x+1) les[max(0,j-1)]++;
	}
	
	
	sort(ALL(R));
	if(R.empty()) {
		_P("-1\n");
	}
	else {
		FOR(i,R.size()) _P("%d%c",R[i],(i==R.size()-1)?'\n':' ');
	}
	
}

まとめ

問題設定は割とシンプルだけど、結構コードがややこしい。