結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2022-07-30 17:23:00 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 972 ms / 1,000 ms |
| コード長 | 11,153 bytes |
| コンパイル時間 | 240 ms |
| 実行使用メモリ | 89,596 KB |
| スコア | 8,229,676 |
| 最終ジャッジ日時 | 2022-07-30 17:23:32 |
| 合計ジャッジ時間 | 31,680 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
from time import time
from math import exp
key = 6
rnd_mod = 12345678901234567891
rnd_x = 9876543210987654321 + 1234567890123456789 * key % rnd_mod
def rnd():
global rnd_x
rnd_x = rnd_x**2 % rnd_mod
return (rnd_x>>10) % (1<<40)
def Randrange(a, b=-1):
if b > 0: return Randrange(b-a) + a
return rnd() % a
def Random():
return Randrange(10 ** 9) / (10 ** 9)
LOCAL = 0
if LOCAL:
N, M = 100, 8
# Seed 0
X = [(477, 514), (703, 786), (577, 572), (327, 487), (951, 516), (782, 153), (423, 656), (341, 549), (754, 45), (317, 592), (588, 809), (644, 212), (451, 345), (716, 164), (497, 469), (391, 287), (618, 266), (26, 823), (637, 896), (688, 549), (566, 337), (826, 239), (145, 711), (28, 842), (715, 744), (714, 318), (758, 619), (727, 621), (533, 162), (385, 510), (336, 570), (794, 449), (510, 297), (110, 735), (767, 199), (619, 759), (563, 934), (822, 469), (645, 160), (154, 696), (580, 315), (788, 431), (164, 693), (315, 598), (568, 538), (802, 587), (863, 314), (776, 382), (408, 398), (421, 516), (445, 931), (180, 673), (540, 640), (711, 706), (702, 132), (560, 849), (849, 534), (363, 608), (914, 550), (413, 460), (526, 972), (436, 608), (807, 469), (517, 430), (699, 191), (755, 440), (192, 680), (329, 669), (22, 793), (314, 564), (505, 688), (579, 899), (746, 727), (820, 722), (495, 510), (611, 883), (171, 838), (441, 639), (715, 707), (843, 324), (643, 689), (736, 456), (527, 582), (383, 593), (173, 655), (823, 428), (867, 203), (183, 810), (468, 333), (514, 821), (727, 356), (847, 655), (578, 519), (638, 794), (866, 292), (695, 69), (987, 620), (961, 610), (844, 399), (811, 678)]
# Seed 1
# X = [(345, 759), (263, 857), (192, 474), (397, 902), (586, 260), (645, 311), (330, 812), (284, 59), (651, 670), (529, 530), (841, 492), (703, 603), (533, 228), (626, 724), (105, 564), (612, 725), (557, 220), (487, 189), (907, 632), (489, 337), (964, 602), (785, 641), (796, 357), (438, 411), (455, 838), (675, 633), (372, 688), (646, 589), (459, 649), (337, 162), (794, 525), (265, 208), (621, 642), (886, 519), (892, 537), (222, 578), (208, 582), (913, 612), (667, 605), (119, 203), (600, 550), (886, 336), (839, 305), (251, 237), (471, 766), (414, 733), (401, 821), (160, 320), (535, 863), (750, 264), (345, 364), (720, 515), (471, 428), (521, 784), (379, 356), (102, 448), (220, 242), (383, 333), (545, 198), (466, 175), (396, 235), (316, 324), (399, 346), (642, 161), (65, 199), (728, 741), (657, 243), (364, 295), (902, 603), (399, 309), (197, 348), (628, 271), (514, 235), (669, 795), (252, 206), (548, 550), (885, 611), (437, 294), (833, 637), (622, 617), (476, 313), (582, 636), (538, 201), (486, 837), (334, 226), (737, 596), (516, 168), (622, 530), (561, 781), (465, 392), (213, 244), (520, 209), (620, 437), (161, 363), (597, 398), (111, 269), (181, 541), (460, 312), (677, 530), (288, 937)]
else:
N, M = map(int, input().split())
X = []
for _ in range(N):
a, b = map(int, input().split())
X.append((a, b))
alpha = 5
alpha2 = alpha ** 2
class State():
def __init__(self, order, station_positions):
self.order = order
self.station_positions = station_positions
def calc_energy(self, beta):
self.pre_calc()
sum_energy = 0
for i, j in zip(self.order, self.order[1:]):
e, d = self.energy_between(i, j)
sum_energy += e + d * beta
return sum_energy
def calc_best_move(self):
self.pre_calc_hist()
L = [(1, 0)]
for i, j in zip(self.order, self.order[1:]):
L += self.best_move_between(i, j)
return L
def nearest(self, i):
mim = -1
x, y = X[i]
s = 10 ** 9
for m, (xx, yy) in enumerate(self.station_positions):
t = (x - xx) ** 2 + (y - yy) ** 2
if t < s:
s = t
mim = m
return mim # , s * alpha
def energy_between(self, i, j):
# energy from planet i to planet j
x1, y1 = X[i]
x2, y2 = X[j]
ii = self.nearest(i)
jj = self.nearest(j)
x3, y3 = self.station_positions[ii]
x4, y4 = self.station_positions[jj]
direct_dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
# i -> j
s = direct_dist * alpha2
# i -> ii -> j
t = ((x1 - x3) ** 2 + (y1 - y3) ** 2) * alpha + ((x2 - x3) ** 2 + (y2 - y3) ** 2) * alpha
if t < s:
s = t
# i -> jj -> j
t = ((x1 - x4) ** 2 + (y1 - y4) ** 2) * alpha + ((x2 - x4) ** 2 + (y2 - y4) ** 2) * alpha
if t < s:
s = t
# i -> ii > jj -> j
t = ((x1 - x3) ** 2 + (y1 - y3) ** 2) * alpha + ((x2 - x4) ** 2 + (y2 - y4) ** 2) * alpha
t += self.dist_between_stations[ii][jj]
if t < s:
s = t
return s, direct_dist
def best_move_between(self, i, j):
x1, y1 = X[i]
x2, y2 = X[j]
ii = self.nearest(i)
jj = self.nearest(j)
x3, y3 = self.station_positions[ii]
x4, y4 = self.station_positions[jj]
# i -> j
s = ((x1 - x2) ** 2 + (y1 - y2) ** 2) * alpha2
L = [(1, j)]
# i -> ii -> j
t = ((x1 - x3) ** 2 + (y1 - y3) ** 2) * alpha + ((x2 - x3) ** 2 + (y2 - y3) ** 2) * alpha
if t < s:
s = t
L = [(2, ii), (1, j)]
# i -> jj -> j
t = ((x1 - x4) ** 2 + (y1 - y4) ** 2) * alpha + ((x2 - x4) ** 2 + (y2 - y4) ** 2) * alpha
if t < s:
s = t
L = [(2, jj), (1, j)]
# i -> ii > jj -> j
t = ((x1 - x3) ** 2 + (y1 - y3) ** 2) * alpha + ((x2 - x4) ** 2 + (y2 - y4) ** 2) * alpha
t += self.dist_between_stations[ii][jj]
if t < s:
s = t
L = [(2, ii), (2, jj), (1, j)]
return L
def pre_calc(self):
dist_between_stations = [[0] * M for _ in range(M)]
for i in range(M):
x1, y1 = station_positions[i]
for j in range(i):
x2, y2 = station_positions[j]
s = (x1 - x2) ** 2 + (y1 - y2) ** 2
if 1:
for k in range(M):
if i == k or j == k:
continue
x3, y3 = station_positions[k]
t = (x1 - x3) ** 2 + (y1 - y3) ** 2 + (x2 - x3) ** 2 + (y2 - y3) ** 2
s = min(s, t)
dist_between_stations[i][j] = s
dist_between_stations[j][i] = s
self.dist_between_stations = dist_between_stations
def pre_calc_hist(self):
dist_between_stations = [[0] * M for _ in range(M)]
hist_between_stations = [[-1] * M for _ in range(M)]
for i in range(M):
x1, y1 = station_positions[i]
for j in range(i):
x2, y2 = station_positions[j]
s = (x1 - x2) ** 2 + (y1 - y2) ** 2
best_h = -1
for k in range(M):
if i == k or j == k:
continue
x3, y3 = station_positions[k]
t = (x1 - x3) ** 2 + (y1 - y3) ** 2 + (x2 - x3) ** 2 + (y2 - y3) ** 2
if t < s:
s = t
best_h = k
dist_between_stations[i][j] = s
dist_between_stations[j][i] = s
hist_between_stations[i][j] = best_h
hist_between_stations[j][i] = best_h
self.dist_between_stations = dist_between_stations
self.hist_between_stations = hist_between_stations
order = [i for i in range(N)] + [0]
station_positions = [(500, 100 * (i + 1)) for i in range(8)]
state = State(order, station_positions)
energy = state.calc_energy(1)
best_energy = 10 ** 18
sTime = time()
time_limit = 180
if not LOCAL:
time_limit = 0.87
T_start = 50000
T_end = 2000
while 1:
progress = ((time() - sTime) / time_limit)
beta = 1 - progress
if progress >= 1:
break
T = T_start * (T_end / T_start) ** progress
if progress < 0.5:
tp = Randrange(-3, 3)
else:
tp = Randrange(-3, 2)
if tp <= 0:
i, j = 0, 0
while i == j:
i = Randrange(1, N + 1)
j = Randrange(1, N + 1)
if i > j:
i, j = j, i
n_order = order[:i] + order[i:j][::-1] + order[j:]
n_state = State(n_order, station_positions)
n_energy = n_state.calc_energy(beta)
if n_energy <= energy or Random() < exp(-min((n_energy - energy) / T, 100)):
order = n_order
state = n_state
energy = n_energy
if progress > 0.3 and LOCAL:
print("Type0", energy, int(10 ** 9 / (energy ** 0.5 + 1000) + 0.5), time() - sTime, "T =", T)
elif tp == 2:
m = Randrange(M)
nx, ny = Randrange(50, 951), Randrange(50, 951)
n_station_positions = station_positions[:]
n_station_positions[m] = (nx, ny)
n_state = State(order, n_station_positions)
n_energy = n_state.calc_energy(beta)
if n_energy <= energy or Random() < exp(-min((n_energy - energy) / T, 100)):
station_positions = n_station_positions
state = n_state
energy = n_energy
if progress > 0.3 and LOCAL:
print("Type1", energy, int(10 ** 9 / (energy ** 0.5 + 1000) + 0.5), time() - sTime, "T =", T)
elif tp == 1:
m = Randrange(M)
x, y = station_positions[m]
ddd = int(50 + (-40) * progress)
dx, dy = Randrange(-ddd, ddd + 1), Randrange(-ddd, ddd + 1)
nx = min(max(x + dx, 0), 1000)
ny = min(max(y + dy, 0), 1000)
n_station_positions = station_positions[:]
n_station_positions[m] = (nx, ny)
n_state = State(order, n_station_positions)
n_energy = n_state.calc_energy(beta)
if n_energy <= energy or Random() < exp(-min((n_energy - energy) / T, 100)):
station_positions = n_station_positions
state = n_state
energy = n_energy
if progress > 0.3 and LOCAL:
print("Type2", energy, int(10 ** 9 / (energy ** 0.5 + 1000) + 0.5), time() - sTime, "T =", T)
else:
assert 0
if energy < best_energy:
best_energy = energy
best_state = state
best_order = order[:]
best_station_positions = station_positions[:]
best_score = int(10 ** 9 / (best_energy ** 0.5 + 1000) + 0.5)
if progress > 0.1 and LOCAL:
print("★ tp =", max(tp, 0), "score =", best_score, "progress =", progress)
if LOCAL:
print("best_energy, best_score =", best_energy, best_score)
print("-" * 50)
print()
for x, y in best_station_positions:
print(x, y)
b = best_state.calc_best_move()
print(len(b))
for t, i in b:
print(t, i + 1)
if LOCAL:
print("-" * 50)
print("best_energy, best_score =", best_energy, best_score)