概要

母船 \((0, 0)\) から宇宙ステーション \((0, W)\) へ、距離 \(D\) 以内のデブリを少なくとも1つ経由して移動するときの最小ジャンプ回数を求める問題です。幅優先探索（BFS）と kd-tree を組み合わせることで、効率的に最短経路を求めます。

考察

グラフ最短経路問題としての定式化

母船、各デブリ、宇宙ステーションを頂点とし、距離が \(D\) 以下の頂点間に辺が存在する無向グラフを考えます。このとき、母船から宇宙ステーションへの最小ジャンプ回数は、重みなしグラフの最短経路問題として幅優先探索（BFS）で求めることができます。

素朴なアプローチの問題点

デブリの個数は \(N \le 10^5\) です。すべてのデブリのペアについて距離を計算して辺を構築しようとすると、\(O(N^2)\) の時間および空間がかかり、実行時間制限（TLE）やメモリ制限（MLE）を超過してしまいます。

解決策

BFSの重要な性質として、「各頂点は高々1度しかキューに追加されない（訪問されない）」という点があります。 したがって、あらかじめグラフのすべての辺を陽に持つ必要はなく、BFSの各ステップで以下のような操作を高速に行えれば十分です：

• クエリ: 点 \((x, y)\) を中心とする半径 \(D\) の円内にある未訪問のデブリをすべて列挙し、訪問済みにする。

2次元平面上の点群に対するこのような幾何的な範囲クエリには、kd-tree（kd木） を利用するのが非常に効果的です。

アルゴリズム

1. kd-tree の構築

   • \(N\) 個のデブリの座標から平衡2分探索木である kd-tree を構築します。
   • 木の深さに応じて、\(x\) 座標と \(y\) 座標の中央値（メディアン）で領域を交互に半分に分割します。
   • 各ノードには、その部分木に含まれるすべての点のバウンディングボックス（最小外接矩形：\([min\_x, max\_x] \times [min\_y, max\_y]\)）と、部分木内に「未訪問の頂点が存在するかどうか」のフラグ has_unvisited を保持させておきます。

2. 範囲クエリの枝刈り（円と矩形の判定）

   • クエリ円の中心 \((cx, cy)\)、半径 \(D\) に対して、ノードの部分木を探索する際に以下の判定を行います：
     1. 探索不要（スキップ）: 部分木内の点がすべて訪問済み（!has_unvisited）である場合。
     2. 円の外側（スキップ）: バウンディングボックスと中心 \((cx, cy)\) の最短距離が \(D\) より大きい場合、この部分木には円内の点が存在しないため探索を打ち切ります。
     3. 円の内側に完全に包含（全回収）: バウンディングボックスと中心 \((cx, cy)\) の最長距離が \(D\) 以下である場合、矩形内のすべての点が円に含まれます。この部分木内の未訪問点を一括して回収します。
     4. 部分的に交差: 現在のノードの点が円内かつ未訪問なら回収し、左右の子ノードを再帰的に探索します。
   • 探索が終わった後、部分木内に未訪問点が残っていなければ has_unvisited = false に更新します。

3. BFS（幅優先探索）

   • 母船 \((0, 0)\) から距離 \(D\) 以内にあるデブリを kd-tree で検索し、距離 \(1\) としてキューに追加します。
   • キューからデブリを取り出し、以下の処理を行います：
     • そのデブリから宇宙ステーション \((0, W)\) までの距離が \(D\) 以下であれば、ゴール可能なので 現在のジャンプ回数 + 1 を出力して終了します。
     • kd-tree を用いて、そのデブリから距離 \(D\) 以内にある未訪問デブリを取得し、距離を更新してキューに追加します。
   • キューが空になっても宇宙ステーションに到達できなければ -1 を出力します。

計算量

• 時間計算量:
  • kd-tree の構築: std::nth_element を用いて \(O(N \log N)\) です。
  • BFS探索: 各頂点は高々1回しか訪問（回収）されず、訪問済みのノードは has_unvisited フラグによって枝刈りされるため、全体として高速に動作します（平均的に \(O(N \log N)\) や \(O(N \sqrt{N})\) 程度）。\(N = 10^5\) に対して実行時間制限内に余裕を持って間に合います。
• 空間計算量: \(O(N)\)
  • kd-tree のノード数、BFS用のキューや距離配列はすべて \(O(N)\) です。

実装のポイント

• オーバーフローの防止:

  • 座標およびジャンプ距離 \(D\) は最大で \(10^9\) です。距離の二乗を計算する際、差の最大値は \(2 \times 10^9\) となり、その二乗の和は最大で約 \(8 \times 10^{18}\) に達します。これは通常の 64bit 符号付き整数型（long long）の最大値（\(\approx 9.22 \times 10^{18}\)）に近いため、二乗の計算には 128bit 整数型（__int128_t）を用いるとオーバーフローを確実に防ぐことができます。

• 完全包含時の高速化 (collect_all):

  • バウンディングボックスが円に完全に含まれる場合、矩形内部の各点の距離計算を省略して一括で訪問済みにすることで、無駄な距離判定を削減し大幅に高速化しています。

    ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

struct Point {
    long long x, y;
    int id;
};

struct Node {
    int pt_idx;
    long long x, y;
    int left = -1, right = -1;
    long long min_x, max_x, min_y, max_y;
    bool has_unvisited = true;
};

vector<Node> nodes;
vector<Point> pts;
vector<bool> visited;

int build(int l, int r, int depth) {
    if (l >= r) return -1;
    int mid = l + (r - l) / 2;
    int axis = depth % 2;
    if (axis == 0) {
        nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r,
            [](const Point& a, const Point& b) {
                return a.x < b.x;
            });
    } else {
        nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r,
            [](const Point& a, const Point& b) {
                return a.y < b.y;
            });
    }

    int u = nodes.size();
    nodes.emplace_back();
    nodes[u].pt_idx = pts[mid].id;
    nodes[u].x = pts[mid].x;
    nodes[u].y = pts[mid].y;
    nodes[u].min_x = nodes[u].max_x = pts[mid].x;
    nodes[u].min_y = nodes[u].max_y = pts[mid].y;

    int left_child = build(l, mid, depth + 1);
    int right_child = build(mid + 1, r, depth + 1);

    nodes[u].left = left_child;
    nodes[u].right = right_child;

    if (left_child != -1) {
        nodes[u].min_x = min(nodes[u].min_x, nodes[left_child].min_x);
        nodes[u].max_x = max(nodes[u].max_x, nodes[left_child].max_x);
        nodes[u].min_y = min(nodes[u].min_y, nodes[left_child].min_y);
        nodes[u].max_y = max(nodes[u].max_y, nodes[left_child].max_y);
    }
    if (right_child != -1) {
        nodes[u].min_x = min(nodes[u].min_x, nodes[right_child].min_x);
        nodes[u].max_x = max(nodes[u].max_x, nodes[right_child].max_x);
        nodes[u].min_y = min(nodes[u].min_y, nodes[right_child].min_y);
        nodes[u].max_y = max(nodes[u].max_y, nodes[right_child].max_y);
    }

    return u;
}

void collect_all(int u, vector<int>& found) {
    if (u == -1 || !nodes[u].has_unvisited) return;
    if (!visited[nodes[u].pt_idx]) {
        visited[nodes[u].pt_idx] = true;
        found.push_back(nodes[u].pt_idx);
    }
    collect_all(nodes[u].left, found);
    collect_all(nodes[u].right, found);
    nodes[u].has_unvisited = false;
}

void query(int u, long long cx, long long cy, long long D, vector<int>& found) {
    if (u == -1 || !nodes[u].has_unvisited) return;

    long long dx = 0;
    if (cx < nodes[u].min_x) dx = nodes[u].min_x - cx;
    else if (cx > nodes[u].max_x) dx = cx - nodes[u].max_x;

    long long dy = 0;
    if (cy < nodes[u].min_y) dy = nodes[u].min_y - cy;
    else if (cy > nodes[u].max_y) dy = cy - nodes[u].max_y;

    if ((__int128_t)dx * dx + (__int128_t)dy * dy > (__int128_t)D * D) {
        return;
    }

    long long max_dx = max(abs(cx - nodes[u].min_x), abs(cx - nodes[u].max_x));
    long long max_dy = max(abs(cy - nodes[u].min_y), abs(cy - nodes[u].max_y));

    if ((__int128_t)max_dx * max_dx + (__int128_t)max_dy * max_dy <= (__int128_t)D * D) {
        collect_all(u, found);
        return;
    }

    if (!visited[nodes[u].pt_idx]) {
        long long dpx = cx - nodes[u].x;
        long long dpy = cy - nodes[u].y;
        if ((__int128_t)dpx * dpx + (__int128_t)dpy * dpy <= (__int128_t)D * D) {
            visited[nodes[u].pt_idx] = true;
            found.push_back(nodes[u].pt_idx);
        }
    }

    query(nodes[u].left, cx, cy, D, found);
    query(nodes[u].right, cx, cy, D, found);

    nodes[u].has_unvisited = !visited[nodes[u].pt_idx] ||
        (nodes[u].left != -1 && nodes[nodes[u].left].has_unvisited) ||
        (nodes[u].right != -1 && nodes[nodes[u].right].has_unvisited);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long W, D;
    if (!(cin >> N >> W >> D)) return 0;

    pts.resize(N);
    vector<long long> orig_x(N), orig_y(N);
    for (int i = 0; i < N; ++i) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i;
        orig_x[i] = pts[i].x;
        orig_y[i] = pts[i].y;
    }

    nodes.reserve(N);
    visited.assign(N, false);
    int root = build(0, N, 0);

    queue<int> q;
    vector<int> dist(N, -1);

    vector<int> initial;
    query(root, 0, 0, D, initial);
    for (int id : initial) {
        dist[id] = 1;
        q.push(id);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        long long to_target_x = 0 - orig_x[u];
        long long to_target_y = W - orig_y[u];
        if ((__int128_t)to_target_x * to_target_x + (__int128_t)to_target_y * to_target_y <= (__int128_t)D * D) {
            cout << dist[u] + 1 << "\n";
            return 0;
        }

        vector<int> nxt;
        query(root, orig_x[u], orig_y[u], D, nxt);
        for (int v : nxt) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    cout << -1 << "\n";
    return 0;
}

この解説は gemini-3.8-flash-high によって生成されました。