ARC102 D - All Your Paths are Different Lengths

問題

以下の条件を満たす有向グラフを1つ作れ
・頂点数20以下で、全ての頂点には1〜Nの相異なる番号が付けられている
・辺数60以下で、全ての辺には0〜10^6の整数の長さが付けられている
・全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向き付けられている
・頂点1から頂点Nへの異なるパスはちょうどl個あり、それらの長さは0からl-1までの相異なる整数である

2 <= l <= 10^6

解法

(思考)
10^6 < Σ2^k (0<=k<=19) より2進数で考えた方が良さそうなのはわかる
(以下数字は全部2進数とする)
例えばl=101011のとき、少なくとも下の写真の黒部分と青部分で長さ0〜011111のパスは全部作れる

100000〜101010はどう作るか？
大きい桁から見ていって、"10...."まで来た場合、"100..."とすればその時点で101010以下なのは確定するからその後の桁は0/1どっちでも良くなる
これを表現するのが写真の赤部分
赤部分の一番左の辺がまさにこの例のように「上位3桁は100で確定させ、残り3桁は自由に決める」ってのを表現してる
ビットが立っている桁ごとにこういう辺を追加すればいい

実装

頂点数は20個で固定しても問題ないから固定した
あと頂点番号は0-basedで考えて、出力するときに+1することにした
mxってのはlでビットが立っている最大の桁数
(builtin_clzで先頭に連なっている0の個数を求め、intのビットサイズ32から引き、更に1引いて0-basedにする)

n未満の全ての頂点vからv+1へ、コスト0の辺を張る(写真黒部分)
→ mx未満の全ての頂点vからv+1へ、コスト2^(mx-v-1)の辺を張る(写真青部分)
→ lのビットを大きい方から見ていき、そのビットが立っている場合のみ写真赤部分のような辺を張る
(lを右にi+1ビットシフトしてから左にi+1ビットシフトして戻すと、lの下位i+1ビットを全て0にしたものが得られるテク)

int l;
vector<pair<pair<int,int>, int> > p;

signed main() {
	cin >> l;
	int mx = 32 - __builtin_clz(l) - 1;
	rep(i,19) p.push_back({{i,i+1},0});
	rep(i,mx) p.push_back({{i, i+1}, 1<<(mx-i-1)});
	for(int i=mx-1;i>=0;i--) {
		int v = mx-i-1;
		if (l&1<<i) p.push_back({{0, v+1}, (l>>(i+1))<<(i+1)});
	}

	cout << 20 << ' ' << p.size() << endl;
	each(i,p) cout << i.first.first+1 << ' ' << i.first.second+1 << ' ' << i.second << endl;
}

「2進数は1桁ずつ(使うか使わないかとかを)決めていく」「途中で元の数字未満ってことが確定したら後の桁はどうでもよくなる(桁dp的な考え)」という2つのスーパー典型の組み合わせって感じ
赤線部分をどうするかで80分も潰したのは良くない
今回結構眠かったので、コンテスト参加時はもっと集中できる状態を作っていきたい