AtCoder ARC #138 (大和証券プログラミングコンテスト2022 Spring) : D - Differ by K bits

なるほど…。
https://atcoder.jp/contests/arc138/tasks/arc138_d

問題

整数N,Kが与えられる。
0～(2^N-1)のPermutationのうち、隣接要素同士が2進数表記でちょうどK桁異なるようなものが存在するなら、その1例を示せ。

解法

Kが偶数の時は解なし。これはpopcountが奇数となる値をPermutation中に置けないことから明らか。
またN=Kの場合、N=1以外では解なし。
以降、Kが奇数かつN未満の場合、構築可能なことを示す。

K=1の場合、グレイコードが解となる。
この考えをもとに、3以上のKについて考えよう。
(2^N)未満の正整数のうち、K bitが立っている要素をN個選び、それらをbit vectorとみなした場合にxorを取ることで0～(2^N-1)を構成できるものを選ぼう。
これは掃き出し法の要領で求めることができる。

こうしてK bitが立っている整数をN個選べた。これをB[i]とする。
次に、Nbitの整数列における、グレイコードを考える。
このグレイコードの値vに対し、vのi bit目が立っているなら、B[i]で置き換える。
(もしvが複数bit立っているなら、対応するB[i]のxorを取る)

こうして作った数列は、隣接要素同士はちょうどB[i]1個分だけ差があるので、K bitの差であることが担保できる。

int N,K;
int A[1<<18];
int vis[1<<18];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	if(N==1) {
		cout<<"Yes"<<endl;
		cout<<"0 1"<<endl;
		return;
	}
	
	if(K%2==0||K==N) {
		cout<<"No"<<endl;
		return;
	}
	
	vector<int> T,cand;
	FOR(i,1<<N) if(__builtin_popcount(i)==K) {
		x=i;
		FORR(t,T) x=min(x,t^x);
		if(x) T.push_back(x), cand.push_back(i);
	}
	
	cout<<"Yes"<<endl;
	FOR(i,1<<N) {
		x=i^(i>>1);
		y=0;
		FOR(j,N) if(x&(1<<j)) y^=cand[j];
		cout<<y<<" ";
	}
	cout<<endl;
	
	
}

まとめ

本番グレイコードは思いついたものの、そこからこの解法に至れず…。