kmjp's blog

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

yukicoder : No.1530 Permutation and Popcount

解法から考えた問題なのかな。
https://yukicoder.me/problems/no/1530

問題

整数列Aに対し、f(A)を以下のように定める。

  • 0≦i,j<Kに対し、popcount(A[i]*A[j])が偶数となる(i,j)の数

整数N,Mが与えられる。
1~Nの正整数を、2つの整数列X,Yに分け、f(X)-f(Y)=Mとなるものを構築せよ。

解法

ある値aに対し、popcount(a*b)が0となる1~Nの範囲のbの個数をP(a)とする。
この時、aがXに入るならf(X)-f(Y)がP(a)/2増え、Yに入るならf(X)-f(Y)がP(a)/2減ると考えることができる。

あとはナップサック問題の要領で、総和がMとなるようにP(a)/2を足すか引くかしていき、最後に復元しよう。

int N,M;
int P[303];

int from[303][400000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	from[0][100000]=1;
	for(i=1;i<=N;i++) {
		for(j=1;j<=N;j++) {
			if(__builtin_popcount(i*j)%2==0) P[i]++;
		}
		FOR(j,200000) if(from[i-1][j]) {
			from[i][j+P[i]]=1;
			from[i][j-P[i]]=-1;
		}
	}
	
	if(from[N][100000+M]==0) {
		cout<<-1<<endl;
	}
	else {
		vector<int> A,B;
		while(N>0) {
			if(from[N][100000+M]==1) {
				A.push_back(N);
				M-=P[N];
			}
			else {
				B.push_back(N);
				M+=P[N];
			}
			N--;
		}
		reverse(ALL(A));
		reverse(ALL(B));
		cout<<A.size()<<" "<<B.size()<<endl;
		FOR(i,A.size()) {
			cout<<A[i];
			if(i==A.size()-1) {
				cout<<endl;
			}
			else {
				cout<<" ";
			}
		}
		FOR(i,B.size()) {
			cout<<B[i];
			if(i==B.size()-1) {
				cout<<endl;
			}
			else {
				cout<<" ";
			}
		}
	}
}

まとめ

2つを掛けたり足したりする条件が出てきたとき、それぞれを独立に考えられるように言い換えるというのは、覚えておくべきテクだな。