結果

問題 No.5007 Steiner Space Travel
ユーザー Kiri8128Kiri8128
提出日時 2022-07-30 17:02:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 966 ms / 1,000 ms
コード長 9,748 bytes
コンパイル時間 563 ms
実行使用メモリ 90,236 KB
スコア 8,009,326
最終ジャッジ日時 2022-07-30 17:02:51
合計ジャッジ時間 32,090 ms
ジャッジサーバーID
(参考情報)
judge10 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 964 ms
86,788 KB
testcase_01 AC 958 ms
87,800 KB
testcase_02 AC 952 ms
88,504 KB
testcase_03 AC 952 ms
88,228 KB
testcase_04 AC 955 ms
88,424 KB
testcase_05 AC 964 ms
88,736 KB
testcase_06 AC 954 ms
88,912 KB
testcase_07 AC 953 ms
88,616 KB
testcase_08 AC 953 ms
87,592 KB
testcase_09 AC 958 ms
86,816 KB
testcase_10 AC 954 ms
89,296 KB
testcase_11 AC 955 ms
87,256 KB
testcase_12 AC 954 ms
89,932 KB
testcase_13 AC 966 ms
88,244 KB
testcase_14 AC 954 ms
87,336 KB
testcase_15 AC 955 ms
88,904 KB
testcase_16 AC 954 ms
87,964 KB
testcase_17 AC 957 ms
87,708 KB
testcase_18 AC 963 ms
87,844 KB
testcase_19 AC 955 ms
88,472 KB
testcase_20 AC 956 ms
87,500 KB
testcase_21 AC 964 ms
87,864 KB
testcase_22 AC 954 ms
86,784 KB
testcase_23 AC 955 ms
88,904 KB
testcase_24 AC 955 ms
87,156 KB
testcase_25 AC 958 ms
88,428 KB
testcase_26 AC 966 ms
88,500 KB
testcase_27 AC 954 ms
87,412 KB
testcase_28 AC 956 ms
88,144 KB
testcase_29 AC 956 ms
90,236 KB
権限があれば一括ダウンロードができます

ソースコード

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, 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 = 3
if not LOCAL:
    time_limit = 0.87

T_start = 1000000
T_end = 1000
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:
        tp = 0
    else:
        tp = Randrange(-3, 3)
    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 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 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 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)
if LOCAL:
    print("-" * 50)
    print("best_energy, best_score =", best_energy, best_score)
0