結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-20 17:51:43 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 918 ms / 1,000 ms |
| コード長 | 8,715 bytes |
| コンパイル時間 | 305 ms |
| コンパイル使用メモリ | 82,260 KB |
| 実行使用メモリ | 90,020 KB |
| スコア | 8,001,540 |
| 最終ジャッジ日時 | 2025-04-20 17:52:13 |
| 合計ジャッジ時間 | 30,208 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
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(point1, point2):
return sum((a - b) ** 2 for a, b in zip(point1, point2)) ** 0.5
# K-meansクラスタリング
def initialize_centroids(points, k):
return random.sample(points, k)
def assign_clusters(points, centroids):
clusters = []
for point in points:
distances = [euclidean_distance(point, centroid) for centroid in centroids]
cluster = distances.index(min(distances))
clusters.append(cluster)
return clusters
def update_centroids(points, clusters, k):
new_centroids = []
for i in range(k):
cluster_points = [points[j] for j in range(len(points)) if clusters[j] == i]
if cluster_points:
new_centroid = [sum(dim) / len(cluster_points) for dim in zip(*cluster_points)]
new_centroids.append(tuple(new_centroid))
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
def HeldKarp(dists):
N = len(dists)
dp = [[10**18] * N for _ in range(2**N)]
for i in range(N):
dp[1<<i][i] = dists[0][i]
for bit in range(1, 1<<N):
for v in range(N):
if not bit & (1<<v):
continue
for nv in range(N):
if bit & (1<<nv) or dists[v][nv] == -1:
continue
dp[bit | (1<<nv)][nv] = min(dp[bit | (1<<nv)][nv], dp[bit][v] + dists[v][nv])
tot_dist = dp[(1<<N) - 1][0]
now = 0
tour = [now]
visited_bit = (1 << N) - 1
dist_sum = tot_dist
EPS = 1e-5
for _ in range(N-1):
visited_bit ^= (1 << now)
for last_city in range(N):
if last_city == now:
continue
if abs(dist_sum - dp[visited_bit][last_city] - dists[last_city][now]) < EPS:
break
else:
assert(False)
dist_sum -= dists[last_city][now]
now = last_city
tour.append(now)
return tot_dist, tour
########################
tk = TimeKeeper()
LIMIT = 0.8
random.seed(0)
ALPHA = 5 # 定数
N, M = map(int, input().split())
points = []
for i in range(N):
x, y = map(int, input().split())
points.append((x, y))
def solve(N, M, ALPHA, points):
def point_edge_decision(p1, p2, station, ALPHA):
"""
p1, p2, station: (x,y) タプル
ALPHA: 重み係数
返り値: (cost, use_station: bool)
"""
d12 = euclidean_distance(p1, p2)
d1s = euclidean_distance(p1, station)
d2s = euclidean_distance(p2, station)
direct = ALPHA**2 * d12
via = ALPHA * (d1s + d2s)
if direct <= via:
return direct, False
else:
return via, True
def calscore(stations, tour, ALPHA):
s = 0
NN = len(tour)
for i in range(NN-1):
type0, id0 = tour[i]
type1, id1 = tour[i+1]
id0 -= 1
id1 -= 1
if type0 == 1:
x0, y0 = id_to_xy[id0]
else:
x0, y0 = stations[id0]
if type1 == 1:
x1, y1 = id_to_xy[id1]
else:
x1, y1 = stations[id1]
d2 = (x0 - x1)**2 + (y0 - y1)**2
if type0 + type1 == 2:
coef = ALPHA**2
elif type0 + type1 == 3:
coef = ALPHA
elif type0 + type1 == 4:
coef = 1
s += d2 * coef
sc = int(10**9 / (1000 + s**0.5) + 0.5)
return sc
# K-meansクラスタリングでM個のクラスに分類
while True:
labels, centroids = kmeans(points, M)
stations = []
for x, y in centroids:
ix, iy = int(x+0.5), int(y+0.5)
stations.append((ix, iy))
if len(stations) == M:
break
# スタート地点のグループが0になるように回転
stt = labels[0]
labels = [(x-stt)%M for x in labels]
for _ in range(stt):
z = stations.pop(0)
stations.append(z)
# グループごとにp, stationの座標を
# ps[i], stations[i]
ps = [[] for _ in range(M)]
id_to_xy = dict()
for i, (x, y) in enumerate(points):
ps[labels[i]].append((x, y, i))
id_to_xy[i] = (x, y)
# print(ps)
# 最短巡回ルート
dists = [[0]*M for _ in range(M)]
for i in range(M):
for j in range(M):
dists[i][j] = euclidean_distance(stations[i], stations[j])
tot_dist, tour_grp = HeldKarp(dists)
# グループごとに解く
tour = []
grp = 0
now = 0
tour.append((1, now+1)) # type, id
x, y = id_to_xy[now]
ps[grp].remove((x, y, now)) # リストから削除
for grp in tour_grp:
station = stations[grp] # ステーション座標
tour.append((2, grp+1)) # ステーション到着
current_coord = station # 今いる場所
# クラスタ内の点を「順番に」回るループ
remaining = ps[grp].copy() # [(x,y,id), ...] のリスト
while remaining:
# 「次に行くべき点」をコスト比較で決定
best = None
best_cost = float('inf')
best_via = False
for x,y, pid in remaining:
cost, via = point_edge_decision(
current_coord,
(x,y),
station,
ALPHA
)
if cost < best_cost:
best_cost = cost
best = (x,y,pid)
best_via = via
# via_station==True なら、ステーション経由でから行く
if best_via and current_coord != station:
# ステーションに一度戻る
tour.append((2, grp+1))
current_coord = station
# 点へ移動
x,y,pid = best
tour.append((1, pid+1))
current_coord = (x,y)
# 処理済みにマーク
remaining.remove(best)
# 最後にステーションに戻る
if current_coord != station:
tour.append((2, grp+1))
tour.append((2, 1))
tour.append((1, 1))
sc = calscore(stations, tour, ALPHA)
# print(sc, file=sys.stderr)
return stations, tour, sc
bestsc = 0
loop = 0
while True:
# print(loop, file=sys.stderr)
if tk.is_time_over(LIMIT):
break
###########
stations, tour, sc = solve(N, M, ALPHA, points)
###########
if sc > bestsc:
print(' best', loop, sc, file=sys.stderr)
bestsc = sc
besttour = tour
beststations = stations
loop += 1
# スコア
print('SC', bestsc, file=sys.stderr)
# 出力（ステーション）
for x, y in beststations:
print(x, y)
# 出力（訪問箇所）
print(len(besttour))
for type, id in besttour:
print(type, id)
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)