結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 dna4_
|
| 提出日時 | 2023-04-25 01:46:19 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 969 ms / 1,000 ms |
| コード長 | 10,674 bytes |
| コンパイル時間 | 634 ms |
| コンパイル使用メモリ | 87,292 KB |
| 実行使用メモリ | 97,856 KB |
| スコア | 8,262,348 |
| 最終ジャッジ日時 | 2023-04-25 01:47:02 |
| 合計ジャッジ時間 | 32,394 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
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(300):
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) -> 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()
#eprint(self.links)
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
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 warshall_floyd(self):
n = len(self.state.planets)
dist = [[INF]*n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for planet1 in self.state.planets:
for planet2 in self.state.planets:
dist[planet1.id][planet2.id] = self.state.cal_dist(planet1, planet2)
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
def solve(self):
dist_matrix = self.warshall_floyd()
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((dist_matrix[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.8)
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))
kmeans = Kmeans(planets, 100, 8)
a = kmeans.clustering()
stations = []
for i in range(input.M):
stations.append(Transit(id = i,x = a[i][0],y = a[i][1],type = 2))
state = State([], planets, stations)
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)
solver = Solver(state)
ans = solver.solve()
score = ans.cal_score()
if score > best_score:
eprint(timeKeeper2.time_msec(), score)
best_score = score
best_ans = ans
tmp_stations = stations
eprint(best_score)
output = Output(best_ans)
output.ans()
if __name__ == "__main__":
main()