yukicoder : No.1880 Many Ways

これは似たような問題を見たことがあったので…。
https://yukicoder.me/problems/no/1880

問題

2^40以下の非負整数Aが与えられる。
以下を満たすN頂点の無向グラフを1つ構成せよ。

• Nは128以下。
• 1番の頂点からN番の頂点への最短経路はA通り

解法

3頂点増やすごとにパターンを倍々にできる構成を考えよう。
以下の上の列は、2頂点ごとにクロスして辺を張る。
そうすると、1→(2,3)→(4,5)→(6,7)…への遷移方法は1→2→4→8通り…と倍々で増えていく。
そこで、Aの2進数表記を考え、下からi番目のbitが立っているなら、下記対応する太字縦棒の部分に辺を張ろう。

 1 -- (2,3) -- (4,5) -- (6,7) -- .... -- (78,79)
┃      ┃      ┃        ┃                ┃
85 --   86  --   87  --   88  --  .... --   125

ll A;
vector<pair<int,int>> E;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	
	FOR(i,40) {
		if(i==0) {
			E.push_back({0,1});
			E.push_back({0,2});
			if(A&(1LL<<i)) E.push_back({0,85});
			E.push_back({85,86});
		}
		else {
			E.push_back({i*2-1,i*2+1});
			E.push_back({i*2-1,i*2+2});
			E.push_back({i*2,i*2+1});
			E.push_back({i*2,i*2+2});
			if(A&(1LL<<i)) {
				E.push_back({i*2-1,85+i});
				E.push_back({i*2,85+i});
			}
			E.push_back({85+i,86+i});
		}
	}
	cout<<E.back().second+1<<" "<<E.size()<<endl;
	FORR2(a,b,E) cout<<a+1<<" "<<b+1<<endl;
}

まとめ

Codeforcesで近い問題見たな。