結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0