結果
| 問題 |
No.5007 Steiner Space Travel
|
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-20 18:29:42 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,967 bytes |
| コンパイル時間 | 452 ms |
| コンパイル使用メモリ | 82,484 KB |
| 実行使用メモリ | 108,652 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-04-20 18:29:48 |
| 合計ジャッジ時間 | 5,357 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 29 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
class TimeKeeper:
def __init__(self):
self.start_time = perf_counter()
def is_time_over(self, LIMIT):
return (perf_counter() - self.start_time) >= LIMIT
def time_now(self):
return (perf_counter() - self.start_time)
def main(DEBUG):
# ユークリッド距離
def euclidean_distance(p1, p2):
return sum((a - b) ** 2 for a, b in zip(p1, p2)) ** 0.5
# K-meansクラスタリング
def initialize_centroids(points, k):
return random.sample(points, k)
def assign_clusters(points, centroids):
clusters = []
for p in points:
ds = [euclidean_distance(p, c) for c in centroids]
clusters.append(ds.index(min(ds)))
return clusters
def update_centroids(points, clusters, k):
new_centroids = []
for i in range(k):
pts = [points[j] for j in range(len(points)) if clusters[j] == i]
if pts:
avg = [sum(dim)/len(pts) for dim in zip(*pts)]
new_centroids.append(tuple(avg))
return new_centroids
def kmeans(points, k, max_iters=100):
centroids = initialize_centroids(points, k)
for _ in range(max_iters):
clusters = assign_clusters(points, centroids)
new_centroids = update_centroids(points, clusters, k)
if centroids == new_centroids:
break
centroids = new_centroids
return clusters, centroids
# Held–Karp TSP
def HeldKarp(dists):
N = len(dists)
dp = [[10**18]*N for _ in range(1<<N)]
for i in range(N):
dp[1<<i][i] = dists[0][i]
for mask in range(1, 1<<N):
for v in range(N):
if not (mask & (1<<v)): continue
for nv in range(N):
if (mask & (1<<nv)) or dists[v][nv] < 0: continue
dp[mask|(1<<nv)][nv] = min(
dp[mask|(1<<nv)][nv],
dp[mask][v] + dists[v][nv]
)
tot = dp[(1<<N)-1][0]
tour = [0]
mask = (1<<N)-1
rem = tot
EPS = 1e-5
cur = 0
for _ in range(N-1):
mask ^= (1<<cur)
for prev in range(N):
if prev == cur: continue
if abs(rem - dp[mask][prev] - dists[prev][cur]) < EPS:
rem -= dists[prev][cur]
cur = prev
tour.append(cur)
break
return tot, tour
# 移動コストの比較
def point_edge_decision(p1, p2, station, ALPHA):
d12 = euclidean_distance(p1, p2)
d1s = euclidean_distance(p1, station)
d2s = euclidean_distance(p2, station)
direct = ALPHA**2 * d12
via = ALPHA * (d1s + d2s)
return (direct, False) if direct <= via else (via, True)
# スコア計算
def calscore(stations, tour, ALPHA):
s = 0
for (t0,i0),(t1,i1) in zip(tour, tour[1:]):
i0 -= 1; i1 -= 1
if t0 == 1:
x0,y0 = id_to_xy[i0]
else:
x0,y0 = stations[i0]
if t1 == 1:
x1,y1 = id_to_xy[i1]
else:
x1,y1 = stations[i1]
d2 = (x0-x1)**2 + (y0-y1)**2
coef = {2:ALPHA**2, 3:ALPHA, 4:1}[t0+t1]
s += d2 * coef
return int(10**9 / (1000 + math.sqrt(s)) + 0.5)
# ツアー構築部を共通化 (固定 labels, stations)
def build_tour_with_fixed(labels, stations):
# 各クラスタ点群と座標辞書
ps = [[] for _ in range(M)]
for i,(x,y) in enumerate(points):
ps[labels[i]].append((x,y,i))
id_to_xy[i] = (x,y)
# グループ間TSP
dists = [[euclidean_distance(stations[i], stations[j])
for j in range(M)] for i in range(M)]
_, tour_grp = HeldKarp(dists)
tour = [(1,1)]
# 点0 を除外
ps[0].remove((id_to_xy[0][0], id_to_xy[0][1], 0))
for grp in tour_grp:
station = stations[grp]
tour.append((2, grp+1))
current = station
rem = ps[grp].copy()
while rem:
best = None
best_cost = float('inf')
best_via = False
for x,y,pid in rem:
cost,via = point_edge_decision(current, (x,y), station, ALPHA)
if cost < best_cost:
best_cost, best = cost, (x,y,pid)
best_via = via
# 経由判定
if best_via and current != station:
tour.append((2, grp+1))
current = station
x,y,pid = best
tour.append((1, pid+1))
current = (x,y)
rem.remove(best)
if current != station:
tour.append((2, grp+1))
tour.append((2,1))
tour.append((1,1))
return tour, calscore(stations, tour, ALPHA)
# solve(): k-means → 回転 → build_tour_with_fixed
def solve(N, M, ALPHA, points):
# k-means
while True:
labels, cents = kmeans(points, M)
stations = []
for x,y in cents:
stations.append((int(x+0.5), int(y+0.5)))
if len(stations) == M:
break
# スタート回転
st0 = labels[0]
labels = [ (c-st0)%M for c in labels ]
stations = stations[st0:] + stations[:st0]
# ツアー構築＆スコア
tour, sc = build_tour_with_fixed(labels, stations)
return labels, stations, tour, sc
# ステーション微調整
def refine_stations(labels, points, stations, ALPHA):
best_st = stations[:]
_, tour0, best_sc = None, None, -1
# 初期評価
tour0, best_sc = build_tour_with_fixed(labels, best_st)
improved = True
deltas = [(-1,0),(1,0),(0,-1),(0,1)]
while improved:
improved = False
for i in range(len(best_st)):
sx, sy = best_st[i]
for dx, dy in deltas:
cand = best_st[:]
cand[i] = (sx+dx, sy+dy)
tour_c, sc_c = build_tour_with_fixed(labels, cand)
if sc_c > best_sc:
best_sc = sc_c
tour0 = tour_c
best_st = cand
improved = True
break
if improved:
break
return best_st, tour0, best_sc
# ------------ main loop ------------
tk = TimeKeeper()
LIMIT = 0.8
random.seed(0)
ALPHA = 5
# 入力
N, M = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(N)]
# グローバル辞書初期化
id_to_xy = {}
best_sc = -1
best_labels = best_stations = best_tour = None
loop = 0
while not tk.is_time_over(LIMIT):
labels, stations, tour, sc = solve(N, M, ALPHA, points)
if sc > best_sc:
best_sc = sc
best_labels, best_stations, best_tour = labels, stations, tour
loop += 1
# ステーション微調整
best_stations, best_tour, best_sc = refine_stations(
best_labels, points, best_stations, ALPHA
)
# 出力
print('SC', best_sc, file=sys.stderr)
for x,y in best_stations:
print(x, y)
print(len(best_tour))
for t,i in best_tour:
print(t, i)
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Debug mode')
parser.add_argument('--debug', action='store_true', help='Enable debug mode')
args = parser.parse_args()
main(args.debug)