結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 dna4_
|
| 提出日時 | 2023-04-25 15:00:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 979 ms / 1,000 ms |
| コード長 | 10,715 bytes |
| コンパイル時間 | 440 ms |
| コンパイル使用メモリ | 87,020 KB |
| 実行使用メモリ | 103,064 KB |
| スコア | 8,291,752 |
| 最終ジャッジ日時 | 2023-04-25 15:01:18 |
| 合計ジャッジ時間 | 32,760 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 970 ms
101,844 KB |
| testcase_01 | AC | 958 ms
97,888 KB |
| testcase_02 | AC | 959 ms
99,480 KB |
| testcase_03 | AC | 958 ms
98,172 KB |
| testcase_04 | AC | 964 ms
98,424 KB |
| testcase_05 | AC | 951 ms
98,632 KB |
| testcase_06 | AC | 964 ms
98,868 KB |
| testcase_07 | AC | 960 ms
98,992 KB |
| testcase_08 | AC | 956 ms
99,568 KB |
| testcase_09 | AC | 954 ms
98,748 KB |
| testcase_10 | AC | 976 ms
99,540 KB |
| testcase_11 | AC | 962 ms
98,972 KB |
| testcase_12 | AC | 978 ms
99,032 KB |
| testcase_13 | AC | 967 ms
97,408 KB |
| testcase_14 | AC | 960 ms
98,980 KB |
| testcase_15 | AC | 964 ms
101,056 KB |
| testcase_16 | AC | 958 ms
99,212 KB |
| testcase_17 | AC | 956 ms
99,580 KB |
| testcase_18 | AC | 963 ms
98,960 KB |
| testcase_19 | AC | 955 ms
98,876 KB |
| testcase_20 | AC | 966 ms
103,064 KB |
| testcase_21 | AC | 973 ms
100,524 KB |
| testcase_22 | AC | 951 ms
100,132 KB |
| testcase_23 | AC | 979 ms
99,012 KB |
| testcase_24 | AC | 974 ms
102,748 KB |
| testcase_25 | AC | 951 ms
98,604 KB |
| testcase_26 | AC | 970 ms
98,316 KB |
| testcase_27 | AC | 972 ms
101,160 KB |
| testcase_28 | AC | 955 ms
100,880 KB |
| testcase_29 | AC | 965 ms
100,936 KB |
ソースコード
import sys
import time
import random
import math
import heapq
from collections import defaultdict
random.seed(42)
INF = 10**18
alpha = 5
alpha2 = alpha * alpha
def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)
class TimeKeeper:
"""
時間を管理するクラス
時間制限を秒単位で指定してインスタンスをつくる
"""
def __init__(self, time_threshold) -> None:
self.start_time_ = time.time()
self.time_threshold_ = time_threshold
def isTimeOver(self) -> bool:
"""
インスタンスを生成した時から指定した時間制限を超過したか判断する
超過している場合にTrue
"""
return time.time() - self.start_time_ - self.time_threshold_ >= 0
def time_msec(self) -> int:
"""経過時間をミリ秒単位で返す"""
return int((time.time() - self.start_time_) * 1000)
def time_sec(self) -> int:
"""経過時間を秒単位で返す(time_msecの使用を推奨)"""
return time.time()-self.start_time_
class Kmeans:
def __init__(self, X:list, n_data:int, k:int):
self.x = [[t.x, t.y] for t in X]
self.n_data = n_data
self.k = k
def init_centroid(self):
idx = random.sample(range(self.n_data), self.k)
centroids = [self.x[i] for i in idx]
return centroids
def compute_distance(self, centroids):
distances = []
for x in self.x:
dist = [math.sqrt(sum([(a - b) ** 2 for a, b in zip(x, centroid)])) for centroid in centroids]
distances.append(dist)
return distances
def clustering(self):
centroids = self.init_centroid()
new_cluster = [0]*self.n_data
cluster = [0]*self.n_data
for epoch in range(100):
distances = self.compute_distance(centroids)
new_cluster = [min(range(len(d)), key=lambda i: d[i]) for d in distances]
for idx_centroid in range(self.k):
x_in_cluster = [self.x[i] for i in range(self.n_data) if new_cluster[i] == idx_centroid]
if x_in_cluster:
centroids[idx_centroid] = [int(sum(coord)/len(x_in_cluster)) for coord in zip(*x_in_cluster)]
if new_cluster == cluster:
break
#cluster = new_cluster
return centroids
class Input:
def __init__(self, N:int, M:int, ab:list) -> None:
self.N = N
self.M = M
self.ab = ab
class Parser:
def __init__(self, input_type:int):
self.flag = input_type
def parse(self):
if self.flag == -1:
inp:Input = self.parse_input()
else:
inp:Input = self.parse_input_file(self.flag)
return inp
def parse_input(self) -> Input:
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N)]
return Input(N,M,ab)
def parse_input_file(self,num) -> Input:
cnt = str(num).zfill(4)
PATH = f"./in/{cnt}.txt"
with open(PATH) as f:
l = [s.strip() for s in f.readlines()]
N, M = map(int,l[0].split())
ab = [list(map(int,s.split())) for s in l[1:]]
return Input(N, M, ab)
class Transit:
def __init__(self, id:int, x:int, y:int, type:int) -> None:
"""
id:int id of planet or station
x:int x coordinate
y:int y coordinate
type:int 1 planet, 2 station
"""
self.id = id
self.x = x
self.y = y
self.type = type
self.key = self.type * 1000 + self.id
def __lt__(self, other) -> bool:
return self.key < other.key
def __eq__(self, other) -> bool:
return self.key == other.key
def __str__(self) -> str:
return f"({self.id},{self.x},{self.y},{self.type})"
class State:
def __init__(self, order:list, planets:list, stations:list, dist_mat:list) -> None:
"""
order:list visited order
stations:list[(int,int)] coordinates of space station
"""
self.order = order
self.planets = planets
self.stations = stations
self.links = self.prepare_edges()
self.dist_mat = dist_mat
def prepare_edges(self):
"""
edges:dictを返す
edges[Transit_from_key:int] = [(dist, Transit_to), ...]
"""
edges = defaultdict(list)
for planet_from in self.planets:
for planet_to in self.planets: # planet to planet
if planet_from == planet_to: continue
edges[planet_from.key].append((self.cal_dist(planet_from, planet_to), planet_to))
for station_to in self.stations: # planet to station
edges[planet_from.key].append((self.cal_dist(planet_from, station_to), station_to))
for station_from in self.stations: # station to station
for planet_to in self.planets:
edges[station_from.key].append((self.cal_dist(station_from, planet_to), planet_to))
for station_to in self.stations:
if station_from == station_to: continue
edges[station_from.key].append((self.cal_dist(station_from, station_to), station_to))
return edges
def cal_dist(self, v1:Transit, v2:Transit) -> float:
"""
return distance between v1 and v2 weighted by coefficient
"""
x1,y1 = v1.x, v1.y
x2,y2 = v2.x, v2.y
coef = alpha
if v1.type == 1 and v2.type == 1: coef = alpha2 # planet to planet
elif v1.type == 2 and v2.type == 2: coef = 1 # station to station
d = ((x1-x2)**2+(y1-y2)**2) * coef
return d
def cal_score(self):
score = 0
for i in range(len(self.order)-1):
score += self.cal_dist(self.order[i], self.order[i+1])
return int(pow(10,9)/(1000+score**0.5))
def trace(start:Transit, target:Transit, ancestors):
# s:source, t:target
# dijksttra法の経路復元
route = [target]
now = target
while True:
pre = ancestors[now.key]
route.append(pre)
if pre == start:
break
now = pre
route.reverse()
return route
def dijkstra(start:Transit, target:Transit, links):
heap = [(*l,start) for l in links[start.key]]
heapq.heapify(heap)
visited = set([start.key])
ancestors = defaultdict(int)
while heap:
cost, to, ancestor = heapq.heappop(heap)
if to.key in visited:
continue
visited.add(to.key)
ancestors[to.key] = ancestor
if to == target:
return cost, trace(start,target,ancestors)
for cost2, node2 in links[to.key]:
if node2.key not in visited:
heapq.heappush(heap, (cost+cost2, node2, to))
return INF, None
def warshall_floyd(planets:list):
n = len(planets)
dist = [[INF]*n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for i in range(n):
for j in range(i+1,n):
d = (planets[i].x - planets[j].x) ** 2 + (planets[i].y - planets[j].y) ** 2
dist[i][j] = d
dist[j][i] = d
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
class Output:
def __init__(self, state:State) -> None:
self.order = state.order
self.stations = state.stations
def ans(self):
for transition in self.stations:
print(transition.x, transition.y)
print(len(self.order))
for transition in self.order:
print(transition.type, transition.id+1)
class Solver:
def __init__(self, state:State) -> None:
self.state = state
def solve(self):
self.state.order.append(self.state.planets[0])
visited = [0]*len(self.state.planets)
visited[0] = 1
now = self.state.planets[0]
next = Transit(-1,-1,-1,-1)
n_visited = set([0])
while len(n_visited) < len(self.state.planets):
next_dist = []
for i in range(len(self.state.planets)):
next_dist.append((self.state.dist_mat[now.id][i], i))
next_dist = sorted(next_dist, key=lambda x:x[0])
for i in range(len(self.state.planets)):
if visited[next_dist[i][1]] == 1: continue
next = self.state.planets[next_dist[i][1]]
break
_, route = dijkstra(now, next, self.state.links)
for transition in route:
self.state.order.append(transition)
now = next
visited[next.id] = 1
n_visited.add(next.id)
_, route = dijkstra(now, self.state.planets[0], self.state.links)
for transition in route:
self.state.order.append(transition)
return self.state
def main():
timeKeeper2 = TimeKeeper(0.83)
parser = Parser(-1)
input = parser.parse()
planets = []
for i in range(input.N):
planets.append(Transit(id = i, x = input.ab[i][0], y = input.ab[i][1], type = 1))
dist_mat = warshall_floyd(planets)
kmeans_center = Kmeans(planets, 100, 8).clustering()
stations = []
for i in range(input.M):
stations.append(Transit(id = i,x = kmeans_center[i][0],y = kmeans_center[i][1],type = 2))
state = State([], planets, stations, dist_mat)
solver = Solver(state)
best_ans = solver.solve()
best_score = best_ans.cal_score()
#eprint(timeKeeper2.time_msec(), best_score)
tmp_stations = best_ans.stations
while not timeKeeper2.isTimeOver():
order = []
stations = []
for i in range(input.M):
x_new = 0
y_new = 0
while True:
x_new = tmp_stations[i].x+random.randrange(-20,20)
y_new = tmp_stations[i].y+random.randrange(-20,20)
if x_new >= 0 and x_new <= 1000 and y_new >= 0 and y_new <= 1000:
break
stations.append(Transit(id = i,x = x_new, y = y_new, type = 2))
state = State(order,planets,stations, dist_mat)
solver = Solver(state)
ans = solver.solve()
score = ans.cal_score()
#eprint(timeKeeper2.time_msec(), score)
if score > best_score:
best_score = score
best_ans = ans
tmp_stations = stations
eprint(best_score)
output = Output(best_ans)
output.ans()
if __name__ == "__main__":
main()