問題

f:id:trsing:20200715212054p:plain D - All Your Paths are Different Lengths

考えたこと

なんかbit的な考え方？という臭いがしたのでとりあえず $2^{N-1}\leq L \lt 2^{N}$ とおき、辺の長さを $2^{i}$ としていい感じの有効グラフを構築してみます。

f:id:trsing:20200715212236p:plain — いい感じの有向グラフ

頂点 $1,N$ 間に長さ $0,\cdots,2^{N-1}-1$ のパスができあがっているので残りの長さ $2^{N-1},\cdots, L-1$ のパスを重複しないように作れないか考えます。

まずは直近の $2^{N-1}$ の辺をどっかの頂点 $k$ から頂点 $N$ に生やしてみます。

f:id:trsing:20200715212347p:plain

頂点 $k$ へのパス長は $0,\cdots,2^{k-1}-1$ ですのでこいつに生やすと頂点 $1$ から頂点 $N$ に長さ $2^{N-1}, \cdots,2^{N-1}+ 2^{k-1}-1$ のパスが出来上がります。

頂点 $k$ の選び方ですが、なるべく多くのパスをカバーしたいので頂点 $N-1$ から逆に見ていくとよさそうです。パス長が $L$ 以上になるならパスして次の頂点 $N-2$ を検討。

頂点 $k$ に辺を生やすと残りのパス長は $2^{N-1}+ 2^{k-1},\cdots ,L-1$ となります。次は $2^{N-1}+2^{k-1}$ の辺を生やします。また $k-1$ から見てやって $L$ 以上にならないものを選ぶ。と繰り返していけばよさそうです。

これで本当にうまくいでしょうか？このやり方だと重複しないようにパスを作れるので、 $0, \cdots, 2^{N-1}-1$ 個の範囲でパスを任意に増やすことができればオッケーです。

頂点 $k$ に生やすと $2^{k-1}$ 個パス長が増えます。 $N$ 以外の頂点に生やせば最大で $\sum_{k=1}^{N-1} 2^{k-1}=2^{N-1}-1$ 個のパスを増やすことができます。好きな $2^{i}$ を選べますのでこの範囲で任意の数のパス長を増やせます。

コード

static void Solve()
{
    var L = Sarray()[0];
    var N = 0;
    for (var i = 0; i < 20; ++i)
        if ((L & (1 << i)) != 0) N = i;
    var graph = Enumerable.Range(0, N).Select(_ => new List<(int to, int c)>()).ToArray();
    for (var i = 0; i < N; ++i)
    {
        graph[i].Add((i + 1, 0));
        graph[i].Add((i + 1, (int)Pow(2, i)));
    }
    var last = L - 1;
    var now = (int)Pow(2, N);
    var pos = N - 1;
    while (now <= last)
    {
        var left = (int)Pow(2, pos) - 1;
        if (now + left <= last)
        {
            graph[pos].Add((N, now));
            now += left + 1;
        }
        --pos;
    }
    var m = graph.Sum(g => g.Count);
    WriteLine($"{N + 1} {m}");
    for (var i = 0; i < N; ++i)
    {
        foreach (var tc in graph[i])
        {
            WriteLine($"{i + 1} {tc.to + 1} {tc.c}");
        }
    }
}