ABC108 D問題 : All Your Paths are Different Lengths

問題. All Your Paths are Different Lengths

整数 $L$ が与えられるので次を満たす多重有向グラフ $G = (V, A)$ とその弧重み $w : A \rightarrow \mathbb{Z}$ を構成せよ．
　・ $|V| \le 20$ ，かつ，頂点のラベルは互いに異なり $1, 2, \ldots, |V|$
　・ $|A| \le 60$ ，かつ，任意の弧 $e \in A$ に対して， $0 \le w(e) \le 10^6$
　・任意の弧 $(i, j) \in A$ に対して， $i < j$
　・頂点1から $|V|$ までの互いに異なるパスはちょうど $L$ 個あり，それらの長さは $0, 1, \ldots, L - 1$

制約： $2 \le L \le 10^6$

解法. 構築ゲー

まず， $2^d \le L < 2^{d+1}$ を満たす $d$ を見つける．このとき，パスの長さが $[0, 2^d)$ を表す有向グラフを構成する．以下では分かりやすさのために， $L = 46$ として説明する． $L = 46$ のとき $d = 5$ となる．
頂点数 $N = d + 1$ で，各 $i \in [1, N)$ に対して，頂点 $i$ から頂点 $i + 1$ への重みが $0$ と $2^{i - 1}$ の異なる弧を2つ加える．
　　　 f:id:tatanaideyo:20180902145712p:plain:w300
このとき，パスの長さは $[0, 2^d)$ まで表現可能であるので，この有向グラフに弧を加えて $[2^d, L)$ を表現可能にすることを考える． $s$ を $L - 2^d$ とする． $s$ を2進数表現で考えて上位ビットから順番に見ていく．初めて1が立っているのが $i_1$ ビット目のとき，頂点 $i_1 + 1$ から頂点 $N$ へ重さ $2^d$ の孤を加える．このとき，頂点1から頂点 $i_1 + 1$ を通ってその弧を通ることによって $[2^d, 2^d + 2^{i_1})$ が表現可能となる．すなわち， $[0, 2^d + 2^{i_1})$ までが表現可能となるので，残りの $[2^d + 2^{i_1}, L)$ までを表現可能にすることを考える． $i_1$ の次に1が立っているビットが $i_2$ ビット目のとき，頂点 $i_2 + 1$ から頂点 $N$ へ重さ $2^d + 2^{i_1}$ の弧を加える．このとき，頂点1から頂点 $i_2 + 1$ を通りその弧を通ることによって， $[2^d + 2^{i_1} , 2^d + 2^{i_1} + 2^{i_2})$ まで表現可能となる．以下同様に $s$ のビットが1となる $j$ 番目の場所 $i_{j}$ に対して頂点 $i_j + 1$ から頂点 $N$ へ重さ $2^d + 2^{i_1} + 2^{i_2} + \cdots + 2^{i_{j-1}}$ の弧を加えると $[0, 2^d + 2^{i_1} + \cdots + 2^{i_{j}})$ まで表現可能なグラフが構成できる．
以上のようにして構成できた有向グラフの頂点数は $L < 2^{20}$ から高々20となる．また，頂点 $i$ から頂点 $i + 1$ へ張られる弧の数は高々3なので，弧数は高々 $3 \times 19 = 57$ となる．
　　　
　　　 f:id:tatanaideyo:20180902153354p:plain:w300

計算時間： $O(1)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int L;
    cin >> L;

    int d = 0;
    for (int p = 2; p <= L; p *= 2) ++d;

    int sum = pow(2, d), res = L - sum;
    const int n = d + 1, m = 2 * d + __builtin_popcount(res);

    cout << n << ' ' << m << '\n';
    for (int i = 1, p = 1; i < n; ++i) {
        cout << i << ' ' << i + 1 << ' ' << 0 << '\n';
        cout << i << ' ' << i + 1 << ' ' << p << '\n';
        p *= 2;
    }

    // add edge : (i + 1) -- sum --> (n)
    for (int i = d - 1; 0 <= i; --i) {
        if (res >> i & 1) {
            cout << i + 1 << ' ' << n << ' ' << sum << '\n';
            sum += pow(2, i);
        }
    }

    return 0;
}

まとめ

構築ゲーは初めてだったので楽しかった．頂点数を抑えるのが難しかった．

参考文献

ARC102解説（2018年9月2日アクセス）