問題概要

$L$ が与えられる。 $N$ 個の頂点と $M$ 個の辺を持ち，かつ頂点 $1$ から頂点 $N$ への異なるパスがちょうど $L$ 個あってそれらのパスがそれぞれ $0, 1, ..., L-1$ であるような有向グラフを構成せよ。

(問題文は https://beta.atcoder.jp/contests/arc102/tasks/arc102_b に記載されている。)

制約

$2 \leq L \leq 10^6$
$2 \leq N \leq 20$
$2 \leq M \leq 60$
辺の重みは $0$ 以上 $10^6$ 以下

アイディア

$10^6$ がだいたい $2^{20}$ であることから $2$ 進数を使うことを考える。

まず，もしも $L = 2^p$ となる整数 $p$ があるならば，次のようなグラフを構成すればよい(画像は $p = 8$ の例)。

f:id:ransewhale:20180902141617p:plain

次に， $2^p \lt L \lt 2^{p+1}$ の場合について考える。

ここではわかりやすく具体的に考えるために $L = 410$ とする。

上の図のグラフで， $0$ 以上 $256$ 未満のパスはすでに生成されている。

次に， $256$ 以上 $410$ 未満のパスについて考える。

$256$ 以上のパスは必ず $256$ 以上なので， $0$ 以上 $154$ 未満のパスについて考えた上で最後に $256$ を足しても問題がない。

ここで，頂点 $1$ から頂点 $8$ までのすべての行き方がちょうど $0$ 以上 $128$ 未満のすべてのパスに一致していることに注目すると，頂点 $8$ から頂点 $9$ に $256$ の辺を張ることでこのグラフに $256$ 以上 $384$ 未満のパスが生成される(次の図は実際に追加した例です)。

f:id:ransewhale:20180902155455p:plain

次に， $384$ 以上 $410$ 未満のパスについて考える。

$384$ 以上のパスは必ず $384$ 以上なので， $0$ 以上 $26$ 未満のパスについて考えた上で最後に $384$ を足しても問題がない。

ここで，頂点 $1$ から頂点 $5$ までのすべての行き方がちょうど $0$ 以上 $16$ 未満のすべてのパスに一致していることに注目すると，頂点 $5$ から頂点 $9$ に $384$ の辺を張ることで $384$ 以上 $400$ 未満のパスが生成される(次の図は実際に追加した例です)。

f:id:ransewhale:20180902155519p:plain

次に， $400$ 以上 $410$ 未満のパスについて考える。

$400$ 以上のパスは必ず $400$ 以上なので， $0$ 以上 $10$ 未満のパスについて考えた上で最後に $400$ を足しても問題がない。

ここで，頂点 $1$ から頂点 $4$ までのすべての行き方がちょうど $0$ 以上 $8$ 未満のすべてのパスに一致していることに注目すると，頂点 $4$ から頂点 $9$ に $400$ の辺を張ることでこのグラフに $400$ 以上 $408$ 未満のパスが生成される(次の図は実際に追加した例です)。

f:id:ransewhale:20180902155532p:plain

最後に， $408$ 以上 $410$ 未満のパスについて考える。

$408$ 以上のパスは必ず $408$ 以上なので， $0$ 以上 $2$ 未満のパスについて考えた上で最後に $408$ を足しても問題がない。

ここで，頂点 $1$ から頂点 $2$ までのすべての行き方がちょうど $0$ 以上 $2$ 未満のすべてのパスに一致していることに注目すると，頂点 $2$ から頂点 $9$ に $408$ の辺を張ることでこのグラフに $408$ 以上 $410$ 未満のパスが生成される(次の図は実際に追加した例です)。

f:id:ransewhale:20180902155545p:plain

これを他の $L$ についても適用することでこの問題を解くことができる。

また，ここで $L \leq 10^6$ であることから $p \leq 19$ であり，頂点が $20$ 個あれば(ギリギリではあるが)グラフを生成することができることがわかる。そして，各頂点から最大で $3$ 個の辺が張られるので，辺の数の条件も満たすことができることがわかる。

実装

まず $L$ を入力として受け取り $2^p \leq L \lt 2^{p+1}$ となる整数 $p$ を求める。このとき，頂点数 $N$ は $p+1$ となる。

次に， $0 \leq i \lt p$ となる各 $i$ に対して，頂点 $i+1$ から頂点 $i+2$ に $0$ と $2^i$ の辺を張る。このとき，辺を $1$ つ追加するたびに辺の数をカウントしておく。

そして， $l = 2^p$ として次のようなループを回す。

$l$ が $L$ 以上ならループを終了する。
$2^t \leq L - l \lt 2^{t+1}$ となる整数 $t$ を求める。
頂点 $t+1$ から頂点 $p+1$ に $l$ の辺を張る。
$l$ に $2^t$ を追加する。

最後に $N, M$ を出力して，そのあと $M$ 行でグラフを出力すればよい。

コード

#include <iostream>
using namespace std;

int N,M=0,u[66],v[66],w[66];

void addedge(int s, int t, int l){
    u[M] = s; v[M] = t; w[M] = l;
    ++M;
}

int l2(int x){
    int l = 0,r = 25,m;
    while(r - l > 1){
        m = (l+r)/2;
        if(x < (1<<m)){
            r = m;
        }else{
            l = m;
        }
    }
    return l;
}

int main(void){
    int L,p,t,i,l;
    cin >> L;
    p = l2(L); N = p+1;
    for(i=0; i<p; ++i){
        addedge(i+1,i+2,0);
        addedge(i+1,i+2,(1<<i));
    }
    l = (1<<p);
    while(l < L){
        t = l2(L-l);
        addedge(t+1,N,l);
        l += (1<<t);
    }
    cout << N << " " << M << endl;
    for(i=0; i<M; ++i){
        cout << u[i] << " " << v[i] << " " << w[i] << endl;
    }
    return 0;
}

(提出したものはこちら)

精進します。

ARC102: D - All Your Paths are Different Lengths

問題概要

制約

アイディア

実装

コード