Day 111-Q4 — Manhattan MST（マンハッタン距離最小全域木・8方向候補辺生成）

2026-08-03 赤色 Master / Phase 8+ ★★★★★★★★★ 8方向スイープ+BITで候補辺をO(N log N)生成しKruskal法

問題

平面上に $N$ 個の点が与えられる。任意の2点間にマンハッタン距離 $|x_i-x_j|+|y_i-y_j|$ を重みとする辺が張られているとき、これらを結ぶ最小全域木の辺重み総和を求めよ。

入力形式

N
x_1 y_1
...
x_N y_N

制約

$1 \le N \le 2\times10^5$
$0 \le x_i,y_i \le 10^9$
座標の重複あり得る

入出力例

入力例1

5
0 0
3 1
1 4
4 4
6 1

出力例1

14

完全グラフのMST重み和は$14$。$N\le5$程度なら全探索でも確認できる。

概念図: 点pを中心とした8方位の候補領域

p ENE NNE NNW WNW WSW SSW SSE ESE 各方位の最近傍点との辺だけを候補にする（最大8N本）

ヒント（段階的開示）

ヒント1: 方向性
完全グラフに素直にKruskal法を適用すると辺数$O(N^2)$で間に合わない。マンハッタン距離のMSTは、各点について8方位それぞれの最近傍点との辺だけを候補にすれば十分という定理が知られている（候補辺は高々$8N$本）。
ヒント2: アプローチ
北東象限では距離が線形式 $(x_q+y_q)-(x_p+y_p)$ になる。これを対角線でさらに2分割した8方位ごとに、掃引順序（ソートキー）とBITでの範囲クエリ（もう1つの制約）を組み合わせ、目的関数の最小値をBITで管理することで、各方位$O(N\log N)$で最近傍候補を求める。8方位分（符号反転4通り×2パターン）繰り返し候補辺を集め、Kruskal法を適用する。
ヒント3: 誘導（コード骨格） 
def run_pattern(points, sx, sy, mode):
    # 座標を(sx*x, sy*y)に変換し、
    # mode='ENE': sweep=(Y-X)昇順, bit_key=Y(接頭辞クエリに変換), obj=X+Y最小化
    # mode='NNE': sweep=(X-Y)昇順, bit_key=X, obj=X+Y最小化
    ...
# sx,syの4通り × mode2通り = 8方位分の候補辺を集めてKruskal法へ

模範解答 (Python)

import sys

def run_pattern(points, sx, sy, mode):
    n = len(points)
    XY = [(sx * x, sy * y, idx) for x, y, idx in points]
    if mode == 'ENE':
        sweep_val = lambda X, Y: Y - X
        bit_val = lambda X, Y: Y
    else:
        sweep_val = lambda X, Y: X - Y
        bit_val = lambda X, Y: X
    order = sorted(range(n), key=lambda i: (sweep_val(XY[i][0], XY[i][1]), -bit_val(XY[i][0], XY[i][1])))
    bvals_sorted = sorted({bit_val(X, Y) for X, Y, _ in XY}, reverse=True)
    rank = {v: i + 1 for i, v in enumerate(bvals_sorted)}
    m = len(bvals_sorted)
    best_val = [float('inf')] * (m + 1)
    best_orig = [None] * (m + 1)

    def update(i, val, orig):
        while i <= m:
            if val < best_val[i]:
                best_val[i] = val
                best_orig[i] = orig
            i += i & (-i)

    def query(i):
        res, o = float('inf'), None
        while i > 0:
            if best_val[i] < res:
                res, o = best_val[i], best_orig[i]
            i -= i & (-i)
        return res, o

    result = [None] * n
    for oi in order:
        X, Y, orig = XY[oi]
        r = rank[bit_val(X, Y)]
        val, cand_orig = query(r)
        if cand_orig is not None:
            result[orig] = (val - (X + Y), cand_orig)
        update(r, X + Y, orig)
    return result

def manhattan_candidates(points):
    n = len(points)
    pts_idx = [(x, y, i) for i, (x, y) in enumerate(points)]
    edges = []
    for sx in (1, -1):
        for sy in (1, -1):
            for mode in ('ENE', 'NNE'):
                res = run_pattern(pts_idx, sx, sy, mode)
                for i in range(n):
                    if res[i] is not None:
                        dist, j = res[i]
                        edges.append((dist, i, j))
    return edges

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def kruskal(n, edges):
    parent = list(range(n))
    total, cnt = 0, 0
    for w, u, v in sorted(edges):
        ru, rv = find(parent, u), find(parent, v)
        if ru != rv:
            parent[ru] = rv
            total += w
            cnt += 1
    return total, cnt

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    points = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1]); idx += 2
        points.append((x, y))
    if n <= 1:
        print(0)
        return
    edges = manhattan_candidates(points)
    total, cnt = kruskal(n, edges)
    print(total)

solve()
計算量: 8方位それぞれ$O(N\log N)$、候補辺は高々$8N$本なのでKruskal法のソートも$O(N\log N)$。全体$O(N\log N)$。4象限のみの誤った実装は$N\le25$の3000ケースで反例（1だけ大きい値）が見つかったが、8方位版は全ケース一致することを確認済み。

Step-by-Step 解説

18方位の最近傍で候補辺が足りる理由
マンハッタン距離は各象限内で線形になる特殊性質を持ち、8方位それぞれの最近傍点だけを候補にすればMSTを再現できることが証明されている（Hwang, 1979）。
2象限をさらに対角線で2分割
北東象限だけでは制約が2つ必要になり単純な1次元スイープ+BITで表現しきれない。対角線でさらに割ることで掃引キーとBITキーがそれぞれ1つの式に対応する。
3掃引順序とBITクエリの対応
ENE方位では$Y-X$昇順の掃引が対角線制約を、$Y\ge Y_p$のBIT接頭辞クエリがもう1つの制約を満たし、この2つから$x_q\ge x_p$も自動的に導かれる。
48方位を符号反転×2パターンで網羅
$(sx,sy)\in\{\pm1\}^2$の4通り×ENE/NNEの2パターンで8方位すべてをカバーする。
5候補辺集合にKruskal法を適用
高々$8N$本の候補辺に通常のKruskal法を適用すれば真のMST重み和が得られる。

よくあるミス

ミス原因正しい書き方
4象限（対角線分割なし）だけで候補辺を作る「象限内は線形」までは正しいが取りこぼす反例が存在する対角線で2分割した8方位すべてで候補辺を作る
同じ掃引キーの点同士が互いの候補にならない単純な掃引順だと同キーの点はまだ未挿入扱いになる同キー内はBITクエリキーの降順で処理し挿入と参照を1点ずつ交互に行う
BITの区間クエリの向きを取り違える「$Y_q\ge Y_p$」を素直に扱おうとして実装を誤る値を降順ランクに変換し接頭辞クエリに帰着させる
座標変換後の値をそのまま出力してしまう変換空間と元の空間を混同するマンハッタン距離は符号反転に不変なので変換空間で計算してよいことを理解する

次のステップ

  • 発展: $u=x+y,v=x-y$ でチェビシェフ距離に変換する別解を試す
  • 発展: オンラインMST維持（Link-Cut Treeで最大辺管理、Day022・Day057）に拡張する
  • 発展: 3次元以上への一般化を検討する

自己評価

自分の回答

気づき・メモ