AtCoder AGC #035 : C - Skolem XOR Tree

色んな解がありそうね。
https://atcoder.jp/contests/agc035/tasks/agc035_c

問題

正整数Nが与えられる。
1～Nのラベルを持つ頂点が2回ずつ登場する連結無向グラフを構築せよ。
その際、同じラベルを持つ頂点間を結ぶパスにおいて、パス上の頂点のラベルのxorを取ると、元の選んだラベルの値と一致しなければならない。

解法

仮に同じラベルaを持つ2頂点のパスを考える場合、
a-b-c-d-...-aとなるが、この時両端のaを除いたラベルのxorはaと一致しなければならない。
とすると、Nが2の累乗の時は解が無い。
N=2^xのとき、a=2^xのケースを考えると、b,c,d...は(2^x)未満なのでxorが2^xになりえないためである。

そうでない場合は必ず解がある。
Nをこえない最大の2のべき乗を2^xとする。
まず2^x未満について条件を満たすものを作ろう。
y=x-1とすると、y未満の整数pについて、p-(p xor (2^y))-(2^y)-p-(p xor (2^y)) と(2^y)を囲うようにpと(p xor (2^y))を並べれば条件を満たす。
p=1～(y-1)についていずれも真ん中の(2^y)を再利用する形で同様に構築しよう。

こうするとどこかに1のラベルができるので、そこを使って(2^x)-(1 xor (2^x))-1-(2^x)-(1 xor (2^x))を配置する。
Nは2のべき乗ではないので、(1 xor (2^x))はN以下に必ず存在する。
こうしてできたグラフにおいて、後者の(2^x)を始点とし、他の頂点を終点とするパスを考えると、xorが(2^x)～*1のラベルを持つ頂点は、そのようなパスの両端にくっつければ良い。

int N;
vector<pair<int,int>> E;
vector<int> EE[201010];
map<int,int> M;

void add(int x,int y) {
	E.push_back({x,y});
	EE[x].push_back(y);
	EE[y].push_back(x);
}

void dfs(int cur,int pre,int v) {
	if(cur>N) v^=(cur-N);
	else v^=cur;
	M[v]=cur;
	FORR(e,EE[cur]) if(e!=pre) dfs(e,cur,v);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if((N&(N-1))==0) return _P("No\n");
	
	x=1;
	while(x*2<=N) x*=2;
	
	cout<<"Yes"<<endl;
	if(N+1==x*2) {
		for(i=1;i<x;i++) {
			add(i,i+x);
			add(i+x,x);
			add(x,i+N);
			add(i+N,i+x+N);
		}
		add(1,x+N);
	}
	else {
		y=x/2;
		for(i=1;i<y;i++) {
			add(i,i+y);
			add(i+y,y);
			add(y,i+N);
			add(i+N,i+y+N);
		}
		add(1,y+N);
		add(x,x+1);
		add(x+1,1);
		add(1,x+N);
		add(x+N,x+1+N);
		
		dfs(x+N,-1,0);
		
		for(i=x+2;i<=N;i++) {
			add(i,x+N);
			assert(M.count(i));
			add(i+N,M[i]);
		}
		
	}
	
	FORR(e,E) cout<<e.first<<" "<<e.second<<endl;
}

まとめ

後半パートはDFSで全列挙することで押し切った。

*1:2^x)+(2^y)-1)をすべて網羅する。（愚直に証明も出来そうだったが、本番は面倒だったのでDFSで列挙した） よって(p xor (2^x