Day 101-Q3 — de Bruijnグラフ上のオイラー閉路構築（Hierholzer法）

2026-07-24 赤色 Master / Phase 8+ ★★★★★★★★★ de Bruijn Sequence構築

問題

アルファベットサイズ $k$、窓幅 $n$ が与えられる。長さ $k^n$ の巡回列であって、長さ $n$ のすべての文字列がちょうど1回ずつ部分文字列として（巡回的に）現れるde Bruijn数列 $B(k,n)$を構築せよ。

de Bruijnグラフ: 頂点は長さ$n-1$の全文字列（$k^{n-1}$個）。各頂点$u$から各文字$c$に対し辺 $u\to(u+c)[1:]$ が張られる（多重辺・自己ループ含む）。各頂点の入次数=出次数=$k$なので必ずオイラー閉路が存在する。

構築（Hierholzer法・小さい文字優先の決定的DFS）:

circuit = []  # 全再帰で共有
def dfs(u):
    for c in 0..k-1（小さい順）:
        if 辺(u,c)未使用:
            使用済みにする
            v = (u + str(c))[1:]
            dfs(v)
            circuit.append(c)   # post-orderで追記
start = "0" * (n-1)
dfs(start)
circuit.reverse()
answer = (start + "".join(circuit))[0 : k**n]

入力形式

k n

制約

$2 \le k \le 8$
$1 \le n \le 5$
$k^n \le 20000$

入出力例

入力例1

2 3

出力例1

00010111

入力例2

2 1

出力例2

01

概念図

B(2,3): 頂点=長さ2の文字列, 辺=長さ3の文字列 00 01 10 11 000 001 010 100 111 101 011 110 全8辺をちょうど1回ずつ通るオイラー閉路 → 00010111

ヒント（段階的開示）

ヒント1: 方向性
「長さ$n$の文字列を頂点にして1文字ずらして重なる関係を辺にする」のはやや筋が悪い。逆に「長さ$n-1$の文字列」を頂点、「長さ$n$の文字列」を辺とみなすと、頂点数$k^{n-1}$・辺数$k^n$の綺麗な有向グラフになり、オイラー閉路の問題に帰着できることに気づけるかがカギ。
ヒント2: アプローチ
de Bruijnグラフでは各頂点の入次数=出次数=$k$なので自動的にオイラー閉路が存在する。Hierholzer法（再帰DFSで、使った辺の文字をpost-orderでリストに積み、最後に全体を反転）で求める。この閉路の文字を順に並べると「開始頂点のラベル＋辺の文字列」という長さ$(n-1)+k^n$の文字列ができ、閉路が出発点に戻るため末尾$n-1$文字が先頭$n-1$文字と一致する。先頭$k^n$文字だけを取れば答え。
ヒント3: 誘導（コード骨格） 
def dfs(u):
    arr = get_used(u)
    for c in range(k):
        if not arr[c]:
            arr[c] = True
            v = (u + str(c))[1:]   # u[1:]+str(c)ではなくこの形で書く
            dfs(v)
            circuit.append(c)

`v = (u + str(c))[1:]`という書き方にしておくと$n=1$（頂点が空文字列）のケースも特別扱いせずに正しく動く。

模範解答 (Python)

import sys


def solve():
    sys.setrecursionlimit(1 << 20)
    k, n = map(int, sys.stdin.read().split())

    used = {}

    def get_used(node):
        if node not in used:
            used[node] = [False] * k
        return used[node]

    circuit = []
    start = "0" * (n - 1)

    def dfs(u):
        arr = get_used(u)
        for c in range(k):
            if not arr[c]:
                arr[c] = True
                v = (u + str(c))[1:]
                dfs(v)
                circuit.append(c)

    dfs(start)
    circuit.reverse()
    seq = "".join(map(str, circuit))
    full = start + seq
    print(full[: k ** n])


solve()
計算量: $O(k^n)$（辺の本数分だけDFSが走る）。

Step-by-Step 解説

1頂点と辺の対応づけ
長さ$n-1$の文字列を頂点、長さ$n$の文字列を辺とみなし、頂点は`dict`で遅延生成。
2決定的DFS
各頂点で小さい文字から順に未使用の辺を試し、出力を一意に定める。
3post-orderで積んで最後に反転
行き止まりから遡って閉路を組み立てる形になり、最後にリスト全体を反転すると正しい走査順が得られる。
4巡回的重複部分の切り捨て
「start+辺の文字列」の末尾$n-1$文字は先頭と一致するため、先頭$k^n$文字だけを取り出す。
5$n=1$の特殊性
`(u+str(c))[1:]`の形で書けば`u=""`のときも正しく空文字列に戻る。

よくあるミス

ミス原因正しい書き方
`v = u[1:] + str(c)`と書く$n\ge2$では動くが$n=1$で壊れる`v = (u + str(c))[1:]`の形で統一
circuitを反転し忘れるpost-order順とそのまま出力すべき順が逆DFS完了後に必ず`circuit.reverse()`
`RecursionError`辺の本数($k^n$)がPythonの再帰上限を超える`sys.setrecursionlimit`を$k^n$より十分大きくする
巡回重複部分を切り捨てずに出力「開始点+辺の文字列」をそのまま答えと誤解`full[:k**n]`で長さ$k^n$に切り詰める

次のステップ

  • 発展: 得られた数列が本当に全長さ$n$文字列を巡回的にちょうど1回ずつ含むか`set`で検証する
  • 発展: 辞書順最小のde Bruijn数列（granddaddy sequence）をFKM algorithmで再現し一致を確認する
  • 次回予告: Lehmer's GCD Algorithm（多倍長整数の高速ユークリッド互除法）

自己評価

自分の回答

気づき・メモ