Codeforces #730 Div2 : E. The Final Pursuit

本番割とすんなり通してるな。
https://codeforces.com/contest/1543/problem/E

問題

N次のHyperCubeがある。
これは0～((2^N)-1)のラベルを持つ頂点を持ち、N*2^(N-1)本の辺からなる。

これに対し、以下の2つの問題に答えよ。

• 辺の集合が与えられるので、HyperCubeの構造を示せ。
• 各頂点をN色で塗ったとする。各点の隣接点は、N通り全色網羅できるか。可能ならその色を示せ。

解法

まず前者を考える。
N次元の座標系を考え、原点と(1,1,...1)を対角線とするHyperCubeを考える。これらの各点に、ラベルを割り当てすることを考えよう。
0番の頂点に隣接するN個の点をそれぞれ、i次の座標が1の点を成すと考えよう。
(1,0,...0)と(0,1,...0)の両方につながる点は、(0,0,...0)と(1,1,.0...0)である、というように考えると、マンハッタン距離が2の異なる点の対から、新たな点のラベルを求めることができる。

後者については、頂点数と辺の数を考えるとNが2の累乗の時のみ条件を満たす彩色が存在する。
これはi番目の軸の座標が1であるようなiのxorを取ると達成できる。
なぜなら、隣接点は1つだけの軸で値が異なるため、上記手順で各頂点の色に対し、隣接点は0～(N-1)とxorを取った値を網羅できるためである。

int T;
int N;

vector<int> E[1<<16];
int mask[1<<16];
int rev[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,1<<N) {
			E[i].clear();
			mask[i]=rev[i]=-1;
		}
		FOR(i,N*(1<<(N-1))) {
			cin>>x>>y;
			E[x].push_back(y);
			E[y].push_back(x);
		}
		mask[0]=rev[0]=0;
		FOR(i,E[0].size()) {
			mask[E[0][i]]=1<<i;
			rev[1<<i]=E[0][i];
		}
		for(int tm=0;tm<1<<N;tm++) if(__builtin_popcount(tm)>=2) {
			x=y=-1;
			FOR(i,N) if(tm&(1<<i)) {
				if(x==-1) x=tm^(1<<i);
				else y=tm^(1<<i);
			}
			int vx=rev[x];
			int vy=rev[y];
			set<int> S,S2;
			FORR(e,E[vx]) if(mask[e]==-1) S.insert(e);
			FORR(e,E[vy]) if(mask[e]==-1&&S.count(e)) S2.insert(e);
			assert(S2.size()==1);
			k=*S2.begin();
			mask[k]=tm;
			rev[tm]=k;
		}
		
		FOR(i,1<<N) cout<<rev[i]<<" ";
		cout<<endl;
		if((N&(N-1))==0) {
			FOR(i,1<<N) {
				x=0;
				FOR(j,N) if(mask[i]&(1<<j)) x^=j;
				cout<<x<<" ";
			}
			cout<<endl;
		}
		else {
			cout<<-1<<endl;
		}
		
		
		
	}
		
}

まとめ

これはすんなり解けてよかったな。