結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2022-07-30 16:44:10 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 899 ms / 1,000 ms |
| コード長 | 9,527 bytes |
| コンパイル時間 | 409 ms |
| 実行使用メモリ | 89,164 KB |
| スコア | 5,670,800 |
| 最終ジャッジ日時 | 2022-07-30 16:44:41 |
| 合計ジャッジ時間 | 30,178 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
from time import time
from math import exp
key = 3
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
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)]
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):
self.pre_calc()
sum_energy = 0
for i, j in zip(self.order, self.order[1:]):
sum_energy += self.energy_between(i, j)
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]
# i -> j
s = ((x1 - x2) ** 2 + (y1 - y2) ** 2) * 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
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(100)] + [0]
station_positions = [(500, 100 * (i + 1)) for i in range(8)]
state = State(order, station_positions)
energy = state.calc_energy()
best_energy = 10 ** 18
sTime = time()
time_limit = 3
if not LOCAL:
time_limit = 0.8
T_start = 1000000
T_end = 10000
while 1:
progress = ((time() - sTime) / time_limit)
if progress >= 1:
break
T = T_start * (T_end / T_start) ** progress
if progress < 0:
tp = 0
else:
tp = Randrange(-2, 3)
if tp <= 0:
i, j = 0, 0
while i == j:
i = Randrange(1, N)
j = Randrange(1, N)
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()
if n_energy <= energy or Random() < exp(-min((n_energy - energy) / T, 100)):
order = n_order
state = n_state
energy = n_energy
if 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()
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 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]
dx, dy = Randrange(-50, 51), Randrange(-50, 51)
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()
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 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 LOCAL:
print("★ tp =", max(tp, 0), "score =", best_score)
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)