問題
平面上に $N$ 個の点が与えられる。続いて $Q$ 個のクエリ点が与えられるので、各クエリについてユークリッド距離が最小となる点（最近傍点）の番号を出力せよ。距離が同じ点が複数ある場合は番号が最も小さいものを出力せよ。
入力形式
N Q
x_1 y_1
:
x_N y_N
qx_1 qy_1
:
qx_Q qy_Q制約
$1 \le N \le 2000$
$1 \le Q \le 2000$
$0 \le x,y \le 10^4$（整数）
同一座標の点あり得る
入出力例
入力例1
5 2
0 0
4 0
2 2
10 10
2 3
2 2
9 9出力例1
3
4クエリ(2,2)は点3(2,2)に距離0で一致。クエリ(9,9)は点4(10,10)が距離√2で最近傍。
概念図：入れ子構造とクエリ枝刈り
ヒント（段階的開示）
ヒント1（方向性）
$N,Q$が小さければ全点との距離計算で通る規模だが、Cover Treeは「点群がどんな距離空間に住んでいてもよい」（次元数ではなく点の局所的な広がり方＝ダブリング次元に依存する）という汎用性が本質的な価値である。
ヒント2（アプローチ）
各ノードは点とレベルiを持ち、子はレベルi-1、親からの距離が$2^i$以内に収まる(covering invariant)。挿入は根から子を辿り「距離$2^i$以内に収まる最も深い場所」を探す。クエリは三角不等式による下界計算で「部分木がどう頑張っても最良距離を更新できない」と判定できたら丸ごと枝刈りする。
ヒント3（誘導）
def insert(node, pts, idx, level):
d = dist(pts, node.idx, idx)
if d > (1 << level):
return False
for c in node.children:
if insert(c, pts, idx, level - 1):
return True
node.children.append(Node(idx, level - 1))
return True
def rec(node):
d = dist_to_query(node)
update_best(d, node.idx)
if d - (1 << (node.level + 1)) > best[0]:
return # 枝刈り
for c in node.children:
rec(c)模範解答 (Python)
import sys
import math
class Node:
__slots__ = ("idx", "level", "children")
def __init__(self, idx, level):
self.idx = idx
self.level = level
self.children = []
def dist(pts, i, j):
ax, ay = pts[i]
bx, by = pts[j]
return math.hypot(ax - bx, ay - by)
def insert(node, pts, idx, level):
d = dist(pts, node.idx, idx)
if d > (1 << level) + 1e-9:
return False
for c in node.children:
if insert(c, pts, idx, level - 1):
return True
node.children.append(Node(idx, level - 1))
return True
def build_cover_tree(pts, root_level):
root = Node(0, root_level)
for i in range(1, len(pts)):
if not insert(root, pts, i, root_level):
root.children.append(Node(i, root_level - 1))
return root
def query_nearest(root, pts, q):
best = [float('inf'), -1]
def rec(node):
qx, qy = q
nx, ny = pts[node.idx]
d = math.hypot(qx - nx, qy - ny)
if d < best[0] - 1e-9 or (best[1] == -1) or (abs(d - best[0]) < 1e-9 and node.idx < best[1]):
if d < best[0] - 1e-9 or best[1] == -1:
best[0], best[1] = d, node.idx
elif abs(d - best[0]) < 1e-9 and node.idx < best[1]:
best[1] = node.idx
subtree_radius = 1 << (node.level + 1)
if d - subtree_radius > best[0] + 1e-9:
return
for c in node.children:
rec(c)
rec(root)
return best[1]
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
Q = int(data[idx]); idx += 1
pts = []
for _ in range(N):
x = int(data[idx]); idx += 1
y = int(data[idx]); idx += 1
pts.append((x, y))
ROOT_LEVEL = 20
root = build_cover_tree(pts, ROOT_LEVEL)
out = []
for _ in range(Q):
x = int(data[idx]); idx += 1
y = int(data[idx]); idx += 1
ans = query_nearest(root, pts, (x, y))
out.append(str(ans + 1))
print("\n".join(out))
main()Step-by-Step 解説
1covering invariantとレベルの意味
レベルiのノードは部分木内の全点が自分から距離$2^i+2^{i-1}+\cdots<2^{i+1}$以内に収まることを保証する。
レベルiのノードは部分木内の全点が自分から距離$2^i+2^{i-1}+\cdots<2^{i+1}$以内に収まることを保証する。
2挿入アルゴリズム（簡略版）
根から子を再帰的に辿り、距離が被覆半径$2^{level}$以内に収まる最初の場所に新しい葉としてぶら下げる。
根から子を再帰的に辿り、距離が被覆半径$2^{level}$以内に収まる最初の場所に新しい葉としてぶら下げる。
3クエリ時の枝刈りの正当性
部分木内のどの点もノードから距離$2^{i+1}$未満にしか存在しえない。三角不等式より $d-2^{i+1}\ge$ best なら部分木を丸ごと枝刈りできる。
部分木内のどの点もノードから距離$2^{i+1}$未満にしか存在しえない。三角不等式より $d-2^{i+1}\ge$ best なら部分木を丸ごと枝刈りできる。
4次元でなく密集度で決まる計算量
理論的な計算量保証は次元数ではなく「ダブリング次元」（点群の局所的な自己相似度）に依存する。
理論的な計算量保証は次元数ではなく「ダブリング次元」（点群の局所的な自己相似度）に依存する。
5計算量
本問規模では全探索O(NQ)でも十分だが、Cover Treeなら理論上、挿入O(N log N)、クエリO(Q log N)に改善できる。
本問規模では全探索O(NQ)でも十分だが、Cover Treeなら理論上、挿入O(N log N)、クエリO(Q log N)に改善できる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ルートレベルを座標の最大値に対して小さく設定し挿入が失敗する | 2^root_levelが最大距離をカバーできていない | 座標の最大差分に対し十分余裕を持ったroot_levelを設定する |
| クエリの枝刈り条件で部分木の半径を$2^{level}$（1項だけ）にしてしまう | 子孫が複数階層に渡って追加される距離の総和を見落とす | 等比級数の和$2^i+2^{i-1}+\cdots<2^{i+1}$を使い1<<(level+1)を上界とする |
| 同点が複数ある場合の挿入で無限ループやスタックオーバーフローする | 距離0の点を子に潜り込ませ続けレベルが際限なく下がる | 距離0の場合の特別扱いや最小レベルでの打ち切りを入れる |
| 最近傍距離が同点の場合のタイブレークを実装し忘れる | 単純な距離比較だけだと同距離の後着が勝ってしまう | 距離が等しい場合は番号が小さい方を優先するロジックを明示的に入れる |
| 再帰版でNが大きいときPythonの再帰上限に達する | Cover Treeの深さは対数オーダーだが極端な入力で深くなりうる | sys.setrecursionlimitを適切に引き上げるか反復に書き換える |
次のステップ
- 発展: $k$近傍（k個の最近傍点）に拡張し、優先度付きキューで探索候補を管理する実装をせよ。
- 発展2: separating invariant も維持する本来のCover Treeを実装し、簡略版との探索ノード数の違いを比較せよ。