E - 宇宙ステーションへの移動 / Traveling to the Space Station 解説 by admin
gpt-6-astra-medium概要
デブリを頂点、距離 \(D\) 以下のデブリ間の移動を辺と考えると、最小ジャンプ回数は幅優先探索（BFS）で求められます。すべての辺を調べる代わりに、デブリを領域ごとに管理する KD 木に似た空間分割木 を使い、到達可能な未訪問のデブリを効率よく探します。
考察
1. 最小ジャンプ回数は BFS で求められる
どのジャンプも、必要な回数は一律で \(1\) です。したがって、母船から \(1\) 回で到達できるデブリ、\(2\) 回で到達できるデブリ、……という順番で探索すれば、最小ジャンプ回数が分かります。
ただし、母船からステーションへの直接移動は禁止されています。そこで、次のように扱います。
- 母船から直接届くデブリを、距離 \(1\) の探索開始点にする。
- デブリからステーションへ届くかを、あらかじめ判定しておく。
- ステーションへ届くデブリを初めて発見したら、そこまでのジャンプ回数に \(1\) を足す。
この方法なら、必ず少なくとも \(1\) つのデブリを経由します。
2. すべてのデブリの組を調べると遅い
素朴には、すべてのデブリの組について距離を計算し、移動可能な組に辺を張れば BFS を実行できます。
しかし、組の数は \(O(N^2)\) です。\(N \leq 10^5\) では、時間も、辺を保存するためのメモリも足りません。
そこで、グラフの辺は明示的に作らず、探索中のデブリから距離 \(D\) 以下にある未訪問のデブリだけを探します。
また、BFS では最初に発見したときに最短距離が確定するため、発見済みのデブリは検索対象から削除できます。
3. 点の集まりを長方形で管理する
点を \(1\) 個ずつ調べる代わりに、複数の点を囲む長方形を考えます。
現在地を中心とする半径 \(D\) の円に対して、長方形の位置関係は次の \(3\) 通りです。
- 長方形全体が円の外側にある
中の点には届かないので、まとめて無視する。 - 長方形全体が円に含まれる
中の点すべてに届くので、まとめて発見する。 - それ以外
長方形をさらに小さな領域に分けて調べる。
この判定を木構造で行うことで、不要な距離計算を減らします。
アルゴリズム
1. 母船・ステーションとの距離を判定する
各デブリ \((x_i,y_i)\) について、次の条件を調べます。
- 母船から届く：\(x_i^2+y_i^2 \leq D^2\)
- ステーションへ届く：\(x_i^2+(W-y_i)^2 \leq D^2\)
両方を満たすデブリがあれば、母船からそのデブリを経由して \(2\) 回で到着できます。直接移動は禁止されているため、これが最適です。
そうでなければ、母船から届くデブリを frontier に入れます。残りのデブリは、ステーションへ届くかどうかのフラグとともに保存します。
この時点で、次のどちらかに該当すれば答えは -1 です。
- 母船から届くデブリがない。
- ステーションへ届くデブリがない。
2. 未訪問のデブリから空間分割木を作る
各ノードは、担当する点を囲む長方形
\([x_{\min},x_{\max}] \times [y_{\min},y_{\max}]\)
を保持します。また、担当する点の中に、ステーションへ届くデブリがあるかも保持します。
木は次のように構築します。
- 点の集合を囲む長方形を求める。
- 点数が \(12\) 以下なら、点をそのまま保存する葉にする。
- そうでなければ、長方形の横幅と縦幅のうち大きい方向を選ぶ。
- その方向の座標でソートし、個数がほぼ等しくなるように二分する。
- それぞれについて再帰的に構築する。
点数で二分するため、木の高さは \(O(\log N)\) になります。
3. 現在地から届く未訪問のデブリを探す
現在地を \((x,y)\) とし、木を根から調べます。
長方形までの最短距離による枝刈り
現在地から長方形までの、各軸方向の最短距離を
\(\delta_x=\max(x_{\min}-x,\ 0,\ x-x_{\max})\)
\(\delta_y=\max(y_{\min}-y,\ 0,\ y-y_{\max})\)
とします。
\(\delta_x^2+\delta_y^2>D^2\)
なら、長方形の中に到達可能な点はありません。そのノード以下の探索を省略します。
長方形全体が届く場合の一括処理
各軸方向の最大距離を
\(\Delta_x=\max(|x-x_{\min}|,\ |x-x_{\max}|)\)
\(\Delta_y=\max(|y-y_{\min}|,\ |y-y_{\max}|)\)
とします。
\(\Delta_x^2+\Delta_y^2\leq D^2\)
なら、長方形内のすべての点に到達できます。
- ステーションへ届く点が含まれていれば、その場で探索を終了する。
- 含まれていなければ、すべての点を次の探索対象
nxtに追加する。 - このノード全体を木から削除する。
どちらでもない場合
葉なら、保存されている各点との距離を直接計算します。到達可能な点を nxt に追加し、葉から削除します。
内部ノードなら、左右の子を再帰的に探索します。
削除後は、空になった部分を取り除き、残った点に合わせて長方形を更新します。これにより、以降の探索でも枝刈りが効きやすくなります。
4. BFS を層ごとに進める
distance を、現在の frontier にあるデブリまでの最小ジャンプ回数とします。初期値は \(1\) です。
frontier の各点から探索し、発見した未訪問のデブリを nxt に集めます。それらはすべて、母船から distance + 1 回で到達できます。
ここでステーションへ届くデブリを発見した場合、答えは
\(\text{distance}+2\)
です。現在のデブリから新しいデブリへ \(1\) 回、そこからステーションへ \(1\) 回ジャンプするためです。
発見できなければ、frontier を nxt に置き換えて次の層へ進みます。探索対象がなくなるまで見つからなければ、-1 を出力します。
正しさ
BFS は、母船からの最小ジャンプ回数が小さい順にデブリを探索します。そのため、未訪問のデブリを初めて発見した時点で、そのデブリへの最小ジャンプ回数が確定します。
空間分割木で探索を省略するのは、長方形全体に届かない場合だけです。また、一括で発見するのは、長方形全体に届く場合だけです。したがって、到達可能な未訪問のデブリを過不足なく発見できます。
よって、ステーションへ届くデブリを最初に発見したときに求めるジャンプ回数が、全体の最小値になります。
計算量
- 時間計算量: 最悪 \(O(N^2)\)。木の構築は \(O(N\log^2 N)\)。
- 空間計算量: \(O(N)\)。
構築では、各ノードで点をソートするため、全体で \(O(N\log^2 N)\) かかります。
探索時間は点の配置と枝刈りの効き方に依存します。各デブリの追加・削除は高々 \(1\) 回ですが、同じ内部ノードを複数回調べることがあるため、探索全体が \(O(N\log N)\) になるとは保証できません。最悪では \(O(N^2)\) ですが、長方形による枝刈りと一括削除によって、実際に調べる量を減らしています。
実装のポイント
平方根は計算しない
距離の二乗を \(D^2\) と比較すれば、浮動小数点誤差を避けて正確に判定できます。発見した時点で検索対象から削除する
同じデブリが複数の探索元から重複してnxtに追加されるのを防ぎます。ステーションへ届くかのフラグは、削除後も更新不要
このコードでは、ステーションへ届くデブリを発見した瞬間に終了します。探索が続く間に削除されるのは、ステーションへ届かないデブリだけなので、ノードのフラグは正しいままです。例外を使って再帰の途中から終了する
Reachedは、ステーションへ届くデブリを発見したことを、再帰呼び出しの外側まで一気に伝えるために使っています。ソースコード
import sys
def main():
input = sys.stdin.buffer.readline
N, W, D = map(int, input().split())
D2 = D * D
frontier = []
remaining = []
has_goal = False
for _ in range(N):
x, y = map(int, input().split())
goal = x * x + (W - y) * (W - y) <= D2
if x * x + y * y <= D2:
if goal:
print(2)
return
frontier.append((x, y, False))
else:
remaining.append((x, y, goal))
has_goal |= goal
if not frontier or not has_goal:
print(-1)
return
def key_x(p):
return p[0]
def key_y(p):
return p[1]
def build(points):
xmin = xmax = points[0][0]
ymin = ymax = points[0][1]
for x, y, _ in points:
if x < xmin:
xmin = x
if x > xmax:
xmax = x
if y < ymin:
ymin = y
if y > ymax:
ymax = y
if len(points) <= 12:
goal = any(p[2] for p in points)
return [xmin, xmax, ymin, ymax, None, None, points, goal]
if xmax - xmin >= ymax - ymin:
points.sort(key=key_x)
else:
points.sort(key=key_y)
mid = len(points) // 2
left = build(points[:mid])
right = build(points[mid:])
return [
xmin, xmax, ymin, ymax,
left, right, None, left[7] or right[7]
]
root = build(remaining)
del remaining
class Reached(Exception):
pass
nxt = []
def search(node, x, y):
xmin, xmax, ymin, ymax = node[0], node[1], node[2], node[3]
if x < xmin:
dx = xmin - x
elif x > xmax:
dx = x - xmax
else:
dx = 0
if y < ymin:
dy = ymin - y
elif y > ymax:
dy = y - ymax
else:
dy = 0
if dx * dx + dy * dy > D2:
return node
dx = x - xmin
t = xmax - x
if t > dx:
dx = t
dy = y - ymin
t = ymax - y
if t > dy:
dy = t
if dx * dx + dy * dy <= D2:
if node[7]:
raise Reached
stack = [node]
while stack:
current = stack.pop()
points = current[6]
if points is not None:
nxt.extend(points)
else:
stack.append(current[4])
stack.append(current[5])
return None
points = node[6]
if points is not None:
size = len(points)
write = 0
for i in range(size):
p = points[i]
dx = p[0] - x
dy = p[1] - y
if dx * dx + dy * dy <= D2:
if p[2]:
raise Reached
nxt.append(p)
else:
points[write] = p
write += 1
if write == 0:
return None
if write == size:
return node
del points[write:]
xmin = xmax = points[0][0]
ymin = ymax = points[0][1]
for px, py, _ in points:
if px < xmin:
xmin = px
if px > xmax:
xmax = px
if py < ymin:
ymin = py
if py > ymax:
ymax = py
node[0] = xmin
node[1] = xmax
node[2] = ymin
node[3] = ymax
return node
left = search(node[4], x, y)
right = search(node[5], x, y)
if left is None:
return right
if right is None:
return left
node[4] = left
node[5] = right
node[0] = left[0] if left[0] < right[0] else right[0]
node[1] = left[1] if left[1] > right[1] else right[1]
node[2] = left[2] if left[2] < right[2] else right[2]
node[3] = left[3] if left[3] > right[3] else right[3]
return node
distance = 1
try:
while frontier and root is not None:
nxt = []
for x, y, _ in frontier:
root = search(root, x, y)
if root is None:
break
frontier = nxt
distance += 1
except Reached:
print(distance + 2)
return
print(-1)
if __name__ == "__main__":
main()
この解説は gpt-6-astra-medium によって生成されました。
投稿日時:
最終更新: