All Your Paths are Different Lengths [AtCoder Regular Contest 102 D]

https://beta.atcoder.jp/contests/arc102/tasks/arc102_b

解法

https://beta.atcoder.jp/contests/arc102/submissions/3127759

「2^20=1048576＞10^6」であるので、いつもの2の累乗を足していく構築テクをもとに考える。
小さいケースで考えてみよう。
L=2^3-1の場合、つまり２進数表記でL=111を作ってみよう。
各桁について0か1かを自由に選択できればいいので、
1->2にコスト0とコスト2^0の辺
2->3にコスト0とコスト2^1の辺
3->4にコスト0とコスト2^2の辺
とすることで、000～111が作れる。
これを拡張することを考える。
　
L=11101である場合、0～1111は上の手法で作っていけばいい。
これで他にカウントすべきは最上位ビットが1の場合の数え上げでる。
なるべくカウントしやすいようにしてみると、10XXX、110XX、11100, 11101の数え上げである（Xは0か1か）。
10XXXを考えてみると、10000+0～111である。
後半部分は上の手法で作れるものに似ている。
上の辺の貼り方を逆にすれば、途中まで辺を貼ってやることによって、上の要望が実現できる。
　
解法は2進数表記した時にdgt桁ある場合はN=dgtにする。
辺のコストは上で説明したのと逆にやる。
1->2にコスト0とコスト2^(dgt-1)の辺
2->3にコスト0とコスト2^(dgt-2)の辺
…
N-1->Nにコスト0とコスト2^0の辺
あとは、1が立っているビットがi桁目であるなら、[dgt,i)桁目はLそのままで[i,1]桁目が全て0の数がコストの辺を1からiに貼る。
こうすることで、(i,1]桁目がXとなる組み合わせ数を全て数え上げることができる。

int L;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L;
 
    int dgt = 1;
    int x = 1;
    while (x <= L) x *= 2, dgt++;
    dgt--;
 
    int N = dgt;
    vector<tuple<int, int, int>> edges;
 
    rep(i, 0, N - 1) {
        edges.push_back(make_tuple(N - i - 1, N - i, 1 << i));
        edges.push_back(make_tuple(N - i - 1, N - i, 0));
    }
 
    rep(i, 0, N - 1) if (L & (1 << i)) {
        int cst = L - (L % (1 << i)) - (1 << i);
        edges.push_back(make_tuple(1, N - i, cst));
    }
 
    int M = edges.size();
    printf("%d %d\n", N, M);
    fore(t, edges) {
        int a, b, c;
        tie(a, b, c) = t;
        printf("%d %d %d\n", a, b, c);
    }
}