解法から考えた問題なのかな。
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つを掛けたり足したりする条件が出てきたとき、それぞれを独立に考えられるように言い換えるというのは、覚えておくべきテクだな。