yukicoder : No.1652 XOR Inequalities

理解するとそこまで難しくないのだが、Editorialが出た後も正答数が少ないのはなぜだろう？
https://yukicoder.me/problems/no/1652

問題

2^N要素の非負整数列Aがある。
一部の要素は未確定である。

未確定の要素に0以上2^30未満の任意の整数値を代入し、A[i ^ j]≧A[i] ^ A[j]を満たすようにしたい。
可能なら一例を構築せよ。

解法

Aを(2進数で)上の桁から決めていく。
上からk+1桁目まで決まったとき、その時点の数列をBとする。
また、これから定めるAのk桁目だけ抜き出した数列をCとする。
Aのうち未確定な要素については、Cも未確定となる。
このCを埋めて行こう。

B[i^j]=B[i]^B[j]となる(i,j)を考える。
最終的にA[i^j]≧A[i]^A[j]でなければならないのでC[i^j]≧C[i]^C[j]でなければならない。
添え字を入れ替えるとC[i]≧C[i^j]^C[j]かつC[j]≧C[i]^C[i^j]を満たさなければならない。
これが満たされるのは、C[i],C[j],C[i^j]のうち0が0,1,3個の時である。
そこで、3つのうち2要素で0が入ることが確定している場合、残り1個を0としよう(逆に、3要素確定済みで0が2個の場面が現れたら解なし)。
未確定なところは、1を埋めておけばよい。

これでC、すなわちAのk桁目が決まる。以後同様に一番下の桁まで繰り返す。

int N;
ll A[1<<7];
ll B[1<<7];
int C[1<<7];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,1<<N) {
		cin>>A[i];
	}
	for(i=29;i>=0;i--) {
		set<pair<int,int>> S;
		FOR(x,1<<N) FOR(y,x) {
			if(((B[x]^B[y])>>i)==(B[x^y]>>i)) {
				S.insert({y,x});
			}
		}
		FOR(x,1<<N) {
			if(A[x]==-1) C[x]=2;
			else C[x]=(A[x]>>i)%2;
		}
		FOR(j,128) {
			FORR2(a,b,S) {
				if(a==0) {
					if(C[b]==0) C[a]=0;
				}
				else {
					if(C[a]==0&&C[b]==0) {
						if(C[a^b]==2) C[a^b]=0;
					}
				}
				
				if(C[a]<2&&C[b]<2&&C[a^b]<2&&C[a^b]<(C[a]^C[b])) {
					cout<<"No"<<endl;
					return;
				}
			}
		}
		FOR(x,1<<N) {
			if(C[x]==2) C[x]=1;
			B[x]|=C[x]<<i;
		}
	}
	cout<<"Yes"<<endl;
	FOR(i,1<<N) cout<<B[i]<<" ";
	cout<<endl;
}

まとめ

言われてみるともともと★３でもそこまで不思議ではない問題。