結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 brthyyjp
|
| 提出日時 | 2023-04-30 14:39:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 950 ms / 1,000 ms |
| コード長 | 7,954 bytes |
| コンパイル時間 | 514 ms |
| コンパイル使用メモリ | 87,320 KB |
| 実行使用メモリ | 90,480 KB |
| スコア | 8,297,973 |
| 最終ジャッジ日時 | 2023-04-30 14:40:23 |
| 合計ジャッジ時間 | 31,585 ms |
|
ジャッジサーバーID （参考情報） |
judge17 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
import math
import random
import os
import io
import sys
from time import time
start_time = time()
input = sys.stdin.readline
random.seed(42)
alpha = 5
mx = 1000
INF = float('inf')
Ts = 50
Te = 10
TIME_LIMIT = 0.85
max_iter = 50
limit = 700
n, m = map(int, input().split())
XY = []
for i in range(n):
x, y = map(int, input().split())
XY.append((x, y))
def kMeans(XY, k):
n = len(XY)
clusters = [random.randint(0, k-1) for i in range(n)]
for _ in range(max_iter):
centroidX = [0]*k
centroidY = [0]*k
clusterCnt = [0]*k
for i, c in enumerate(clusters):
clusterCnt[c] += 1
centroidX[c] += XY[i][0]
centroidY[c] += XY[i][1]
for c in range(k):
if clusterCnt[c] == 0:
centroidX[c] = random.randint(0, mx)
centroidY[c] = random.randint(0, mx)
else:
centroidX[c] //= clusterCnt[c]
centroidY[c] //= clusterCnt[c]
newClusters = [-1]*n
for i in range(n):
mn = INF
nc = -1
x, y = XY[i]
for c in range(k):
d = (x-centroidX[c])**2+(y-centroidY[c])**2
if d < mn:
mn = d
nc = c
newClusters[i] = nc
clusters = newClusters
return centroidX, centroidY
CD = []
centroidX, centroidY = kMeans(XY, m)
for c, d in zip(centroidX, centroidY):
CD.append((c, d))
XY += CD
def calc_energy(i, j):
xi, yi = XY[i]
xj, yj = XY[j]
d2 = (xi-xj)**2+(yi-yj)**2
if 0 <= i < n and 0 <= j < n:
return (alpha**2)*d2
elif n <= i < n+m and n <= j < n+m:
return d2
else:
return alpha*d2
g = [[] for i in range(n+m)]
dist_table = [[INF]*(n+m) for i in range(n+m)]
for i in range(n+m):
for j in range(n+m):
if i == j:
continue
x1, y1 = XY[j]
dist = calc_energy(i, j)
g[i].append((dist, j))
dist_table[i][j] = dist
def calc_dist(path, dist_table):
res = 0
for v, nv in zip(path, path[1:]):
res += dist_table[v][nv]
return res
def nearest_neighbor(s, g):
nonvisit = set(range(n))
path = []
path.append(s)
nonvisit.remove(s)
while nonvisit:
min_dist = INF
nx = -1
for d, v in g[path[-1]]:
if not v in nonvisit:
continue
if d < min_dist:
min_dist = d
nx = v
path.append(nx)
nonvisit.remove(nx)
return path+[s]
def anealing(path, dist_table, Ts, Te, time_limit, threshold, method_selection):
while True:
now_time = time()
if now_time - start_time > time_limit:
return path
# insert station
if random.random() > threshold:
i = random.randint(0, len(path)-2)
u, v = path[i], path[i+1]
min_dist = dist_table[u][v]
nx = -1
for k in range(m):
w = n+k
dist = dist_table[u][w]+dist_table[w][v]
if dist <= min_dist:
min_dist = dist
nx = w
diff = min_dist-dist_table[u][v]
temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
prob = math.exp(min(700, -diff / temp))
if prob > random.random():
if nx != -1:
path = path[0:i+1]+[nx]+path[i+1:]
else:
# 2-opto
if random.random() > method_selection:
i = random.randint(0, len(path)-4)
p1 = path[i]
p2 = path[i+1]
p_dist = dist_table[p1][p2]
j = random.randint(i+2, len(path)-2)
q1 = path[j]
q2 = path[j+1]
q_dist = dist_table[q1][q2]
q_dist = dist_table[q1][q2]
cur_dist = p_dist + q_dist
new_dist = dist_table[p1][q1]+dist_table[p2][q2]
diff = new_dist-cur_dist
temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
prob = math.exp(min(700, -diff / temp))
if prob > random.random():
sep1, sep2, sep3 = path[:i+1], path[i+1:j+1], path[j+1:]
sep2.reverse()
path = sep1+sep2+sep3
# or-opto
else:
tar_section = random.randint(1, len(path)-3)
saki = random.randint(0, len(path)-2)
if tar_section-1 <= saki <= tar_section+1:
continue
a = tar_section-1
b = tar_section
c = tar_section+1
d = tar_section+2
e = saki
f = saki+1
pa, pb, pc, pd = path[a], path[b], path[c], path[d]
pe, pf = path[e], path[f]
cur_dist = dist_table[pa][pb] + \
dist_table[pc][pd]+dist_table[pe][pf]
new_dist1 = dist_table[pa][pd] + \
dist_table[pe][pb]+dist_table[pc][pf]
new_dist2 = dist_table[pa][pd] + \
dist_table[pe][pc]+dist_table[pb][pf]
rev = new_dist1 > new_dist2
mn_new_dist = min(new_dist1, new_dist2)
diff = mn_new_dist-cur_dist
temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
prob = math.exp(min(700, -diff / temp))
if prob > random.random():
if not rev:
if c < e:
sep1 = path[:a+1]
sep2 = path[d:e+1]
sep3 = path[b:c+1]
sep4 = path[f:]
path = sep1+sep2+sep3+sep4
else:
sep1 = path[:e+1]
sep2 = path[b:c+1]
sep3 = path[f:a+1]
sep4 = path[d:]
path = sep1+sep2+sep3+sep4
else:
if c < e:
sep1 = path[:a+1]
sep2 = path[d:e+1]
sep3 = path[b:c+1]
sep3.reverse()
sep4 = path[f:]
path = sep1+sep2+sep3+sep4
else:
sep1 = path[:e+1]
sep2 = path[b:c+1]
sep2.reverse()
sep3 = path[f:a+1]
sep4 = path[d:]
path = sep1+sep2+sep3+sep4
path = nearest_neighbor(0, g)
path = anealing(path, dist_table, Ts, Te, 0.5, 1, 0.1)
path = anealing(path, dist_table, Ts, Te, TIME_LIMIT, 0.7, 0.5)
xSum = [0]*m
ySum = [0]*m
connectCnt = [0]*m
for p in range(len(path)-1):
i, j = path[p], path[p]
if i > j:
i, j = j, i
if i >= n and j >= n:
continue
if i < n and j < n:
continue
sj = j-n
xSum[sj] += XY[i][0]
ySum[sj] += XY[i][1]
connectCnt[sj] += 1
for j in range(m):
if connectCnt[j] == 0:
continue
nx = int(xSum[j]/connectCnt[j])
ny = int(ySum[j]/connectCnt[j])
CD[j] = (nx, ny)
XY[j+n] = (nx, ny)
#dist_table = [[INF]*(n+m) for i in range(n+m)]
#for i in range(n+m):
#for j in range(n+m):
#if i == j:
#continue
#x1, y1 = XY[j]
#dist = calc_energy(i, j)
#dist_table[i][j] = dist
#s = calc_dist(path, dist_table)
#score = round(10**9/(1000+math.sqrt(s)))
#print(score, file=sys.stderr, flush=True)
for c, d in CD:
print(c, d)
print(len(path))
for k in range(len(path)):
r = path[k]
if 0 <= r < n:
print(1, r+1)
else:
print(2, r-n+1)