色んな解がありそうね。
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