結果

問題 No.5007 Steiner Space Travel
ユーザー Kiri8128Kiri8128
提出日時 2022-07-30 17:17:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 967 ms / 1,000 ms
コード長 11,100 bytes
コンパイル時間 325 ms
実行使用メモリ 90,004 KB
スコア 8,126,957
最終ジャッジ日時 2022-07-30 17:18:00
合計ジャッジ時間 31,766 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 956 ms
88,368 KB
testcase_01 AC 958 ms
90,004 KB
testcase_02 AC 967 ms
88,608 KB
testcase_03 AC 956 ms
87,960 KB
testcase_04 AC 955 ms
88,256 KB
testcase_05 AC 954 ms
89,228 KB
testcase_06 AC 954 ms
87,024 KB
testcase_07 AC 955 ms
88,144 KB
testcase_08 AC 959 ms
86,724 KB
testcase_09 AC 955 ms
87,208 KB
testcase_10 AC 955 ms
87,852 KB
testcase_11 AC 959 ms
87,788 KB
testcase_12 AC 966 ms
87,340 KB
testcase_13 AC 954 ms
87,684 KB
testcase_14 AC 956 ms
89,188 KB
testcase_15 AC 956 ms
87,028 KB
testcase_16 AC 957 ms
87,764 KB
testcase_17 AC 967 ms
89,164 KB
testcase_18 AC 955 ms
86,912 KB
testcase_19 AC 956 ms
88,324 KB
testcase_20 AC 955 ms
87,624 KB
testcase_21 AC 960 ms
87,392 KB
testcase_22 AC 964 ms
86,304 KB
testcase_23 AC 956 ms
89,764 KB
testcase_24 AC 956 ms
87,992 KB
testcase_25 AC 957 ms
89,456 KB
testcase_26 AC 956 ms
88,336 KB
testcase_27 AC 955 ms
89,464 KB
testcase_28 AC 957 ms
88,452 KB
testcase_29 AC 953 ms
86,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from time import time
from math import exp
key = 5
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]
        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(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)
0