Day 070-Q2 — SMAWK応用・凸4分探索（Divide & Conquer + 2D最近点ペア O(NlogN)）

2026-06-23 赤色 Master / Phase 8+ ★★★★★★★★★ SMAWK・単調行列・分割統治最適化・マンハッタン距離

問題

$N$ 個の点 $P_1, \ldots, P_N$（$x$ 昇順 $y$ 昇順にソート済み）と $M$ 個の点 $Q_1, \ldots, Q_M$（同じく $x$ 昇順 $y$ 昇順）が与えられる。

各 $Q_j$ に対し、マンハッタン距離 $|x_{Q_j} - x_{P_i}| + |y_{Q_j} - y_{P_i}|$ が最小となる $P_i$ への距離を求めよ。

ただし $P, Q$ ともに $x, y$ 座標が単調増加する（コスト行列が完全単調）という特殊条件下では、分割統治最適化で全体 $O((N+M)\log N)$ が実現できる。

制約

パラメータ範囲
$N, M$$1 \le N, M \le 2 \times 10^5$
座標$-10^9 \le x, y \le 10^9$（整数）
単調条件$P$ は $x$ 昇順かつ $y$ 昇順、$Q$ も同様

入出力例

入力例 1

4 3
1 2
3 5
6 7
9 10
2 3
5 6
8 9

出力例 1

1
1
1

入力例 2

3 3
0 0
5 5
10 10
1 1
6 4
9 11

出力例 2

0
2
1

概念図: 分割統治最適化の単調性利用

単調性: Q_j に対する最近 P_i のインデックス opt(j) は j が増えるにつれ単調増加 ⟹ 分割統治: 中央クエリの最近点を求め、左側の探索範囲を右端、右側の探索範囲を左端で制限 各レベルで O(N+M) 仕事、深さ O(log M) → 全体 O((N+M)log M) dc(ql=0, qr=6, pl=0, pr=7) の再帰展開 Level 0: qmid=3, P[0..7] を走査 → opt(3)=3 が判明 左再帰: dc(0, 2, 0, 3) | 右再帰: dc(4, 6, 3, 7) Level 1L: qmid=1, P[0..3] 走査 → opt(1)=1 dc(0,0,0,1) | dc(2,2,1,3) Level 1R: qmid=5, P[3..7] 走査 → opt(5)=5 dc(4,4,3,5) | dc(6,6,5,7) dc(0,0,0,1): Q[0] の答え dc(2,2,1,3): Q[2] の答え dc(4,4,3,5): Q[4] の答え dc(6,6,5,7): Q[6] の答え 計算量の確認: 各レベルで処理される (Q範囲長) + (P範囲長) の和 = O(M + N)（単調性により P 範囲が重複しない） 深さ O(log M) なので全体 O((N+M) log M) ナイーブ O(NM) から大幅改善（N=M=2×10⁵ で約 10¹⁰ → 約 5×10⁶）

ヒント（段階的開示）

ヒント1: 方向性
$P, Q$ ともに $x, y$ が単調増加のとき、コスト行列 $C[j][i] = \mathrm{dist}(Q_j, P_i)$ は完全単調（totally monotone）になり、各行の最小値インデックスが単調増加する。これを分割統治で利用する。
ヒント2: アプローチ
分割統治最適化:
  1. クエリ範囲 $[ql, qr]$ の中央 $qmid$ を選ぶ
  2. $P[pl..pr]$ を線形走査して $Q[qmid]$ の最近点 $best\_i$ を見つける
  3. 左再帰: $dc(ql, qmid-1, pl, best\_i)$（P の右端を $best\_i$ で制限）
  4. 右再帰: $dc(qmid+1, qr, best\_i, pr)$（P の左端を $best\_i$ から開始）
ヒント3: コード骨格 
def dc(ql, qr, pl, pr):
    if ql > qr: return
    qmid = (ql + qr) // 2
    best_i, best_d = pl, float('inf')
    for i in range(pl, pr + 1):
        d = manhattan(P[i], Q[qmid])
        if d < best_d:
            best_d = d; best_i = i
    result[qmid] = best_d
    dc(ql, qmid - 1, pl, best_i)
    dc(qmid + 1, qr, best_i, pr)

dc(0, M - 1, 0, N - 1)

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    P = []
    for _ in range(N):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        P.append((x, y))

    Q = []
    for _ in range(M):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        Q.append((x, y))

    def manhattan(p, q):
        return abs(p[0] - q[0]) + abs(p[1] - q[1])

    result = [0] * M

    def dc(ql, qr, pl, pr):
        if ql > qr:
            return
        qmid = (ql + qr) // 2
        best_i = pl
        best_d = float('inf')
        for i in range(pl, pr + 1):
            d = manhattan(P[i], Q[qmid])
            if d < best_d:
                best_d = d
                best_i = i
        result[qmid] = best_d
        dc(ql, qmid - 1, pl, best_i)
        dc(qmid + 1, qr, best_i, pr)

    dc(0, M - 1, 0, N - 1)
    print(*result, sep='\n')

solve()

Step-by-Step 解説

Step 1: 単調性の証明

$P, Q$ ともに $x, y$ が単調増加のとき、$Q_j$ に対する最近 $P_i$ のインデックス $\mathrm{opt}(j)$ は $j$ が増えると単調増加する（コスト行列の逆三角不等式から証明）。

Step 2: 分割統治最適化の構造

単調性を利用して探索範囲を絞る。各レベルで P 範囲の和が $O(N)$、Q 範囲の和が $O(M)$ → 全体 $O((N+M)\log M)$。

Step 3: マンハッタン距離の場合の単調性

$x, y$ 共に単調増加なら $\mathrm{dist}(Q_j, P_i)$ のコスト行列は inverse Monge 行列になり、各行最小値インデックスが単調増加する。

Step 4: SMAWK との関係

SMAWK アルゴリズムは完全単調行列の全行最小値を $O(N+M)$ で求める。分割統治版は $O((N+M)\log)$ だが実装が簡単。

Step 5: 計算量比較

手法計算量実装難易度
ナイーブ$O(NM)$易
分割統治最適化$O((N+M)\log M)$中
SMAWK$O(N+M)$難

よくあるミス

ミス原因正しい書き方
右再帰の pl を best_i+1 にするbest_i は右側でも使える可能性があるdc(qmid+1, qr, best_i, pr)
単調性の前提を確認せず適用任意入力では誤答問題の単調条件を必ず確認
再帰深度が Python 制限を超える$M = 2 \times 10^5$ で深さ $\log_2 M \approx 17$ なので問題なし必要なら sys.setrecursionlimit
SMAWK と分割統治の混同SMAWK は $O(N+M)$、分割統治は $O((N+M)\log)$問題サイズに応じて選択

次のステップ

  • 発展問題: 完全単調行列の SMAWK 実装（$O(N+M)$ を実現）
  • 1D-1D DP 最適化（Knuth 最適化・四辺形不等式）との統一理解
  • 並列二分探索との組み合わせ
  • $k$-nearest neighbor を分割統治で解く

自己評価