E - 宇宙ステーションへの移動 / Traveling to the Space Station Editorial by admin
Claude Opus 5 (High)概要
始点 \((0,0)\) から、距離 \(D\) 以内のデブリへ次々にジャンプして、ゴール \((0,W)\) へ到達する最小ジャンプ回数を求める問題です。辺が「距離 \(D\) 以内」という幾何的条件で暗黙に定まる巨大なグラフ上での BFS（幅優先探索）を、\(N \le 10^5\) に間に合う形で行うのが本質です。
考察
グラフとしての定式化
頂点を「母船 \((0,0)\)」「各デブリ \((x_i,y_i)\)」「ステーション \((0,W)\)」とし、距離が \(D\) 以下の \(2\) 点間に重み \(1\) の辺を張ります。ただし「母船 → ステーション」の直接辺だけは禁止（必ずデブリを \(1\) つ以上経由）です。
すべての辺の重みが \(1\) なので、最小ジャンプ回数は BFS で求まります。
素朴なアプローチの問題点
素直にやると、全頂点対について距離を計算して隣接リストを作ることになります。辺の本数は最悪 \(O(N^2) = 10^{10}\) であり、時間も空間も全く足りません。
たとえば全デブリが半径 \(D\) の小さな領域に密集していれば、本当に \(\Theta(N^2)\) 本の辺が存在してしまうので、「隣接リストを作らない」工夫が必要です。
突破口：BFS では各頂点は一度しか使わない
BFS の重要な性質として、一度距離が確定した頂点は二度と更新されない、ということがあります。つまり、頂点 \(u\) を展開するときに欲しいのは
「\(u\) から距離 \(D\) 以内にある、まだ未訪問のデブリ全体」
だけです。すでに訪問済みの点を何度も列挙することが無駄なのです。
そこで、
- 点集合を空間的に分割するデータ構造（kd-tree）を持つ
- 「ある点から半径 \(D\) 以内の点を列挙する」円形領域クエリを行う
- 列挙して訪問済みにした点は、データ構造から削除する
という方針を取ります。すると、各点は生涯にわたって高々 \(1\) 回しか「取り出される」ことがないので、列挙コストの合計は \(O(N)\) に抑えられます。残るのは「領域を走査したが何も取れなかった」分のオーバーヘッドだけで、これは kd-tree で「生存点数 \(0\) の部分木は即打ち切る」ことで実用的な速度になります。
これは「削除付き近傍探索で BFS を行う」という定番テクニックです（グリッド分割やセグメント木＋set でも同様のことができます）。
アルゴリズム
デブリの座標配列に対して kd-tree を構築する。
- 各ノードは担当する点の区間 \([l, r)\)、その領域のバウンディングボックス（\(x, y\) の最小・最大）、そして 生存点数
aliveを持つ。 - 分割は、\(x\) 方向と \(y\) 方向のうち広がりが大きい軸を選び、
nth_elementで中央値分割する（葉は \(16\) 点程度でまとめる）。
- 各ノードは担当する点の区間 \([l, r)\)、その領域のバウンディングボックス（\(x, y\) の最小・最大）、そして 生存点数
円形領域クエリ
query(点 q)：- ノードの
alive == 0なら即 return（削除済みの塊をスキップ）。 - \(q\) からノードのバウンディングボックスまでの最短距離が \(D\) を超えるなら即 return（枝刈り）。
- 葉なら、区間内の未訪問点を線形に見て、距離 \(\le D\) のものを結果リストに追加し、
aliveを減らす。 - 内部ノードなら左右を再帰し、
aliveを子から再計算する。
- ノードの
BFS：
- まず \((0,0)\) からクエリして、見つかった点の距離を \(1\) とし、キューに入れる（同時に kd-tree からは削除された状態になる）。
- キューから \(u\) を取り出し、\(u\) の座標でクエリ。見つかった点の距離を \(\mathrm{dist}(u)+1\) としてキューに入れる。
- キューが空になるまで繰り返す。
答えの算出：
- 全デブリ \(i\) について、\(\mathrm{dist}(i)\) が確定しており、かつ \(i\) から \((0,W)\) までの距離が \(D\) 以下なら、\(\mathrm{dist}(i)+1\) が答えの候補。
- その最小値を出力。候補がなければ
-1。 - この「最後に必ずデブリを経由してからゴールへ飛ぶ」という形にしておくことで、「母船→ステーション直接ジャンプ禁止」という制約が自動的に満たされます。
計算量
kd-tree の削除付き円形クエリを \(N+1\) 回行いますが、取り出される点の総数は \(O(N)\) です。走査オーバーヘッドを含めた実用的な見積りは以下の通りです。
- 時間計算量: 構築 \(O(N \log N)\)、BFS 全体で平均的に \(O(N \sqrt{N})\) 程度（最悪ケースは理論上より大きくなり得るが、
aliveによる枝刈りにより \(N = 10^5\) では十分高速） - 空間計算量: \(O(N)\)
実装のポイント
距離比較は必ず二乗のまま行う：
sqrtを使うと誤差と速度の両方で損をします。\(dx^2+dy^2 \le D^2\) で比較します。オーバーフローに注意：\(|x| \le 10^9\)、\(W \le 10^9\)、\(D \le 10^9\) なので、\(dx^2\) は最大 \(4\times10^{18}\) 程度になります。
long long（64bit）で計算しましょう。\(D^2 \le 10^{18}\) もlong longに収まります。aliveの管理：葉で点を取り出したら葉のaliveを減らし、再帰から戻るときに内部ノードのaliveを子の和で更新します。これがないと、既に全部訪問済みの領域を何度も走査してしまい TLE します。バウンディングボックスと点の最短距離：軸ごとに「\(q\) が区間の外側にある分だけ」を距離として足します（区間内なら \(0\)）。
dx = max(0, minx - qx, qx - maxx) dy = max(0, miny - qy, qy - maxy)葉のサイズ：\(1\) 点ごとに葉を作るとノード数・再帰オーバーヘッドが増えるため、\(16\) 点程度でまとめると定数倍が改善します。
入出力の高速化：\(N = 10^5\) 行の入力なので、
getchar_unlockedによる自前の整数読み込みやscanfを使うと安全です。到達不能の判定：BFS 後に \((0,W)\) へ飛べるデブリが一つも訪問されていなければ
-1。デブリの \(y_i\) は \(1 \le y_i \le W-1\) なので、デブリがステーションと同じ点に重なることはありません。ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll minx, maxx, miny, maxy; int l, r, lc, rc, alive; };
static vector<Node> tr;
static vector<pair<ll,ll>> pts;
static vector<int> dst;
static ll D2;
static vector<int> found_;
int build(int l, int r) {
int id = (int)tr.size();
tr.push_back(Node());
ll mnx = LLONG_MAX, mxx = LLONG_MIN, mny = LLONG_MAX, mxy = LLONG_MIN;
for (int i = l; i < r; i++) {
mnx = min(mnx, pts[i].first); mxx = max(mxx, pts[i].first);
mny = min(mny, pts[i].second); mxy = max(mxy, pts[i].second);
}
tr[id].minx = mnx; tr[id].maxx = mxx; tr[id].miny = mny; tr[id].maxy = mxy;
tr[id].l = l; tr[id].r = r; tr[id].alive = r - l; tr[id].lc = tr[id].rc = -1;
if (r - l <= 16) return id;
int m = (l + r) / 2;
if (mxx - mnx >= mxy - mny)
nth_element(pts.begin()+l, pts.begin()+m, pts.begin()+r,
[](const pair<ll,ll>&a, const pair<ll,ll>&b){ return a.first < b.first; });
else
nth_element(pts.begin()+l, pts.begin()+m, pts.begin()+r,
[](const pair<ll,ll>&a, const pair<ll,ll>&b){ return a.second < b.second; });
int lc = build(l, m);
int rc = build(m, r);
tr[id].lc = lc; tr[id].rc = rc;
return id;
}
void query(int id, ll qx, ll qy) {
Node &n = tr[id];
if (n.alive == 0) return;
ll dx = 0, dy = 0;
if (qx < n.minx) dx = n.minx - qx; else if (qx > n.maxx) dx = qx - n.maxx;
if (qy < n.miny) dy = n.miny - qy; else if (qy > n.maxy) dy = qy - n.maxy;
if (dx*dx + dy*dy > D2) return;
if (n.lc < 0) {
int cnt = 0;
for (int i = n.l; i < n.r; i++) {
if (dst[i] != -1) continue;
ll ddx = pts[i].first - qx, ddy = pts[i].second - qy;
if (ddx*ddx + ddy*ddy <= D2) { found_.push_back(i); cnt++; }
}
n.alive -= cnt;
return;
}
int lc = n.lc, rc = n.rc;
query(lc, qx, qy);
query(rc, qx, qy);
tr[id].alive = tr[lc].alive + tr[rc].alive;
}
static inline int readInt() {
int c = getchar_unlocked();
while (c != '-' && (c < '0' || c > '9')) c = getchar_unlocked();
int sgn = 1;
if (c == '-') { sgn = -1; c = getchar_unlocked(); }
long long x = 0;
while (c >= '0' && c <= '9') { x = x*10 + (c - '0'); c = getchar_unlocked(); }
return (int)(x * sgn);
}
int main() {
int N = readInt();
ll W = readInt();
ll D = readInt();
D2 = D * D;
pts.resize(N);
for (int i = 0; i < N; i++) {
ll x = readInt();
ll y = readInt();
pts[i] = {x, y};
}
tr.reserve(2 * (N / 8 + 4));
int root = build(0, N);
dst.assign(N, -1);
found_.reserve(N);
vector<int> q;
q.reserve(N);
found_.clear();
query(root, 0, 0);
for (int p : found_) { dst[p] = 1; q.push_back(p); }
size_t head = 0;
while (head < q.size()) {
int u = q[head++];
found_.clear();
query(root, pts[u].first, pts[u].second);
int du = dst[u];
for (int p : found_) { dst[p] = du + 1; q.push_back(p); }
}
long long ans = LLONG_MAX;
for (int i = 0; i < N; i++) {
if (dst[i] < 0) continue;
ll dx = pts[i].first - 0;
ll dy = pts[i].second - W;
if (dx*dx + dy*dy <= D2) ans = min(ans, (long long)dst[i] + 1);
}
if (ans == LLONG_MAX) printf("-1\n");
else printf("%lld\n", ans);
return 0;
}
この解説は claude5opus-high によって生成されました。
posted:
last update: