Codeforces #558 Div2 E. Magical Permutation

Eは本番なんとか解けたけど割と苦戦した。
https://codeforces.com/contest/1163/problem/E

問題

整数の集合Sが与えられる。
ある非負整数xに対し、0～(2^x-1)からなるpermutationのうち、隣接要素のxorがS内のいずれかになるようにしたい。
なお、xorを取った値が同じものが複数回登場しても問題ない。

条件を満たすPermutationのうち、xが最大の物を1つ答えよ。

解法

xを大きい順に総当たりすることを考える。
Sのうち2^x未満の要素において、要素をx bitのbit vectorとみなしたとき、互いに線形独立となる要素をx個求めよう。
これは単純にガウスの掃出し法で求められる。

そのような要素がx個見つかった場合、隣接要素がそのx個のいずれかになるようなPermutationを構築しよう。
前述の要素からなる数列をV[i]とする。
P[0]=0とし、以後P[i]をP[i]=P[i-1] xor V[f(i)]とする。f(i)はiの2進数表記においてビットが立っている最下位の位置とする。

こうすると、P[0]～P[(2^x)-1]には、V[0]～V[x-1]のべき集合のそれぞれxorを取ったもの2^x通りが列挙され、条件を満たす。
感覚的にはグレイコードの構築法で、隣接要素の差がV[0]～V[x-1]のいずれかであると考えればよいか。

int N;
int S[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	
	for(y=20;y>=0;y--) {
		vector<vector<int>> V;
		FOR(i,N) {
			if(S[i]>=1<<y) continue;
			int lef=S[i];
			FORR(v,V) if(lef&(1<<v[2])) lef^=v[1];
			if(lef) {
				x=0;
				FOR(j,20) if(lef&(1<<j)) x=j;
				FORR(v,V) if(v[1]&(1<<x)) v[1]^=lef;
				V.push_back({S[i],lef,x});
			}
		}
		if(V.size()<y) continue;
		cout<<y<<endl;
		cout<<0;
		int cur=0;
		for(i=1;i<1<<y;i++) {
			FOR(j,y) if(i&(1<<j)) {
				cur ^= V[j][0];
				cout<<" "<<cur;
				break;
			}
		}
		cout<<endl;
		break;
	}
	
	
}

まとめ

こちらは面白い問題だったね。