問題

問題文

https://atcoder.jp/contests/abc108/tasks/arc102_b

問題概要

整数 $L$ が与えられる.

以下の条件を満たす有向グラフをひとつ構成せよ. グラフは多重辺を含んでもよい.

条件を満たす有向グラフの存在は保証されている.

頂点数 $N$ が 20 以下で全ての頂点は 1以上N以下の番号が付けられている.
辺の数 M は 60以下で全ての辺には0以上10⁶以下の重み(コスト)がついている.
全ての辺は番号の小さい頂点から大きい頂点に向かって張られている.
頂点 1 から頂点 N への異なるパスはちょうど L 個あり、それらの長さは 0 から L-1 までの相異なる整数である

制約

$2 \leqq L \leqq 10^{6}$

解答例

指針

長さ 0 の辺と長さが2冪の辺を張る.

解説

以下のように頂点 i から頂点 i + 1 へ, 長さ 0 の辺と長さ 2^i-1 の辺を 1 本ずつ張ると長さ 0~2^N-1-1 までの相異なるパスをもつ有向グラフを構成できる.

f:id:kira000:20190118025144p:plain

パスはちょうど L 個にするにはまず, $2^{r} \leqq L$ を満たす最大の r を求め, 頂点数 r+1 のときの上のようなグラフを構成する.

構成したグラフのある頂点 v から頂点 N に長さ X の辺を張ったときのことを考える.

このとき追加されるパスは, 長さが X, X+1, ... X+2^v−1−1 となる合計 2^v-1 のパスである.

例えば, 上の例で 3から5へ長さ X のパスを追加すると, X, X+1, X+2, X+3 のパスを追加できる.

f:id:kira000:20190118030553p:plain

したがって頂点 v を大きい方から見ていき, 足りないパスを追加していくということを繰り返すことで要求されたグラフを構成できる.

C++ による実装例

// submission: https://atcoder.jp/contests/abc108/submissions/4033499
// Language: C++14 (GCC 5.4.1)
// Time: 1 ms
// Memoly: 256 KB

#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
struct edge {
    ll src, dst, cost;
    edge() {}
    edge(ll a, ll b, ll c) : src(a), dst(b), cost(c) {}
};
 
int main() {
    ll L, r = 1;
    ll N = 0, M;
    vector<edge> G;
 
    cin >> L;
 
    while (r <= L) {
        r *= 2;
        N++;
    }
    for (ll i = 1; i < N; i++) {
        G.push_back( edge(i, i+1, 0) );
        G.push_back( edge(i, i+1, (1<<(i-1))) );
    }
 
    ll remain = L - (1<<(N-1));
 
    for (ll i = N-1; i >= 1; i--) {
        if (!remain) { break; }
 
        if ( remain >= (1 << (i-1)) ) {
            G.push_back( edge(i, N, L-remain) );
            remain -= (1 << (i-1));
        }
    }
 
    M = G.size();
 
    cout << N << " " << M << endl;
 
    for (auto &e: G) {
        cout << e.src << " " << e.dst << " " << e.cost << endl;
    }
 
    return 0;
}

Python3 による実装例

# submission: https://atcoder.jp/contests/abc108/submissions/4033507
# Language: Python3 (3.4.3)
# Time: 18 ms
# Memoly: 3064 KB

L = int(input())
 
N, r = 0, 1
 
while r <= L:
    r *= 2
    N += 1
 
G = []
for i in range(1, N):
    G.append( [i, i+1, 0] )
    G.append( [i, i+1, int(2**(i-1))] )
 
remain = L - int(2**(N-1))
 
for i in range(N-1, 0, -1):
    if remain == 0:
        break
 
    if remain >= int(2**(i-1)): 
        G.append( [i, N, L-remain] )
        remain -= int(2**(i-1))
 
print (N, len(G))
 
for i in G:
    print (" ".join(map(str, i)))