結果

問題 No.5007 Steiner Space Travel
ユーザー brthyyjpbrthyyjp
提出日時 2023-04-30 18:54:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 986 ms / 1,000 ms
コード長 7,998 bytes
コンパイル時間 653 ms
コンパイル使用メモリ 86,180 KB
実行使用メモリ 92,084 KB
スコア 8,299,288
最終ジャッジ日時 2023-04-30 18:55:03
合計ジャッジ時間 32,494 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 979 ms
92,084 KB
testcase_01 AC 981 ms
90,072 KB
testcase_02 AC 977 ms
89,552 KB
testcase_03 AC 986 ms
91,368 KB
testcase_04 AC 978 ms
91,224 KB
testcase_05 AC 982 ms
91,728 KB
testcase_06 AC 977 ms
90,208 KB
testcase_07 AC 980 ms
91,772 KB
testcase_08 AC 981 ms
88,844 KB
testcase_09 AC 976 ms
89,396 KB
testcase_10 AC 981 ms
89,404 KB
testcase_11 AC 986 ms
90,288 KB
testcase_12 AC 980 ms
88,312 KB
testcase_13 AC 979 ms
90,456 KB
testcase_14 AC 977 ms
89,880 KB
testcase_15 AC 979 ms
90,980 KB
testcase_16 AC 977 ms
87,856 KB
testcase_17 AC 979 ms
88,608 KB
testcase_18 AC 976 ms
90,512 KB
testcase_19 AC 977 ms
89,128 KB
testcase_20 AC 984 ms
90,464 KB
testcase_21 AC 977 ms
91,140 KB
testcase_22 AC 976 ms
90,912 KB
testcase_23 AC 979 ms
89,112 KB
testcase_24 AC 976 ms
88,820 KB
testcase_25 AC 983 ms
88,236 KB
testcase_26 AC 980 ms
91,292 KB
testcase_27 AC 979 ms
91,060 KB
testcase_28 AC 978 ms
89,576 KB
testcase_29 AC 979 ms
91,544 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import random
import os
import io
import sys
from time import time
start_time = time()

input = sys.stdin.readline


random.seed(42)
alpha = 5
mx = 1000
INF = float('inf')
Ts = 50
Te = 10
TIME_LIMIT = 0.88

max_iter = 50

limit = 700

n, m = map(int, input().split())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))


def kMeans(XY, k):
    n = len(XY)
    clusters = [random.randint(0, k-1) for i in range(n)]
    for _ in range(max_iter):
        centroidX = [0]*k
        centroidY = [0]*k
        clusterCnt = [0]*k
        for i, c in enumerate(clusters):
            clusterCnt[c] += 1
            centroidX[c] += XY[i][0]
            centroidY[c] += XY[i][1]
        for c in range(k):
            if clusterCnt[c] == 0:
                centroidX[c] = random.randint(0, mx)
                centroidY[c] = random.randint(0, mx)
            else:
                centroidX[c] //= clusterCnt[c]
                centroidY[c] //= clusterCnt[c]
        newClusters = [-1]*n
        for i in range(n):
            mn = INF
            nc = -1
            x, y = XY[i]
            for c in range(k):
                d = (x-centroidX[c])**2+(y-centroidY[c])**2
                if d < mn:
                    mn = d
                    nc = c
            newClusters[i] = nc
        clusters = newClusters
    return centroidX, centroidY


CD = []
centroidX, centroidY = kMeans(XY, m)
for c, d in zip(centroidX, centroidY):
    CD.append((c, d))

XY += CD


def calc_energy(i, j):
    xi, yi = XY[i]
    xj, yj = XY[j]
    d2 = (xi-xj)**2+(yi-yj)**2
    if 0 <= i < n and 0 <= j < n:
        return (alpha**2)*d2
    elif n <= i < n+m and n <= j < n+m:
        return d2
    else:
        return alpha*d2


g = [[] for i in range(n+m)]
dist_table = [[INF]*(n+m) for i in range(n+m)]
for i in range(n+m):
    for j in range(n+m):
        if i == j:
            continue
        x1, y1 = XY[j]
        dist = calc_energy(i, j)
        g[i].append((dist, j))
        dist_table[i][j] = dist


def calc_dist(path, dist_table):
    res = 0
    for v, nv in zip(path, path[1:]):
        res += dist_table[v][nv]
    return res


def nearest_neighbor(s, g):
    nonvisit = set(range(n))
    path = []
    path.append(s)
    nonvisit.remove(s)
    while nonvisit:
        min_dist = INF
        nx = -1
        for d, v in g[path[-1]]:
            if not v in nonvisit:
                continue
            if d < min_dist:
                min_dist = d
                nx = v
        path.append(nx)
        nonvisit.remove(nx)
    return path+[s]


def anealing(path, dist_table, Ts, Te, time_limit, threshold, method_selection):
    while True:
        now_time = time()
        if now_time - start_time > time_limit:
            return path
        # insert station
        if random.random() > threshold:
            i = random.randint(0, len(path)-2)
            u, v = path[i], path[i+1]
            min_dist = dist_table[u][v]
            nx = -1
            for k in range(m):
                w = n+k
                dist = dist_table[u][w]+dist_table[w][v]
                if dist <= min_dist:
                    min_dist = dist
                    nx = w
            diff = min_dist-dist_table[u][v]
            temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
            prob = math.exp(min(700, -diff / temp))
            if prob > random.random():
                if nx != -1:
                    path = path[0:i+1]+[nx]+path[i+1:]
        else:
            # 2-opto
            if random.random() > method_selection:
                i = random.randint(0, len(path)-4)
                p1 = path[i]
                p2 = path[i+1]
                p_dist = dist_table[p1][p2]
                j = random.randint(i+2, len(path)-2)
                q1 = path[j]
                q2 = path[j+1]
                q_dist = dist_table[q1][q2]
                q_dist = dist_table[q1][q2]
                cur_dist = p_dist + q_dist
                new_dist = dist_table[p1][q1]+dist_table[p2][q2]
                diff = new_dist-cur_dist
                temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
                prob = math.exp(min(700, -diff / temp))
                if prob > random.random():
                    sep1, sep2, sep3 = path[:i+1], path[i+1:j+1], path[j+1:]
                    sep2.reverse()
                    path = sep1+sep2+sep3
            # or-opto
            else:
                tar_section = random.randint(1, len(path)-3)
                saki = random.randint(0, len(path)-2)
                if tar_section-1 <= saki <= tar_section+1:
                    continue
                a = tar_section-1
                b = tar_section
                c = tar_section+1
                d = tar_section+2
                e = saki
                f = saki+1
                pa, pb, pc, pd = path[a], path[b], path[c], path[d]
                pe, pf = path[e], path[f]
                cur_dist = dist_table[pa][pb] + \
                    dist_table[pc][pd]+dist_table[pe][pf]
                new_dist1 = dist_table[pa][pd] + \
                    dist_table[pe][pb]+dist_table[pc][pf]
                new_dist2 = dist_table[pa][pd] + \
                    dist_table[pe][pc]+dist_table[pb][pf]
                rev = new_dist1 > new_dist2
                mn_new_dist = min(new_dist1, new_dist2)
                diff = mn_new_dist-cur_dist
                temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
                prob = math.exp(min(700, -diff / temp))
                if prob > random.random():
                    if not rev:
                        if c < e:
                            sep1 = path[:a+1]
                            sep2 = path[d:e+1]
                            sep3 = path[b:c+1]
                            sep4 = path[f:]
                            path = sep1+sep2+sep3+sep4
                        else:
                            sep1 = path[:e+1]
                            sep2 = path[b:c+1]
                            sep3 = path[f:a+1]
                            sep4 = path[d:]
                            path = sep1+sep2+sep3+sep4
                    else:
                        if c < e:
                            sep1 = path[:a+1]
                            sep2 = path[d:e+1]
                            sep3 = path[b:c+1]
                            sep3.reverse()
                            sep4 = path[f:]
                            path = sep1+sep2+sep3+sep4
                        else:
                            sep1 = path[:e+1]
                            sep2 = path[b:c+1]
                            sep2.reverse()
                            sep3 = path[f:a+1]
                            sep4 = path[d:]
                            path = sep1+sep2+sep3+sep4


path = nearest_neighbor(0, g)
path = anealing(path, dist_table, Ts, Te, 0.3, 1, 0.1)
path = anealing(path, dist_table, Ts, Te, 0.7, 0.7, 0.2)
path = anealing(path, dist_table, Ts, Te, TIME_LIMIT, 0.9, 1)

xSum = [0]*m
ySum = [0]*m
connectCnt = [0]*m
for p in range(len(path)-1):
    i, j = path[p], path[p]
    if i > j:
        i, j = j, i
    if i >= n and j >= n:
        continue
    if i < n and j < n:
        continue
    sj = j-n
    xSum[sj] += XY[i][0]
    ySum[sj] += XY[i][1]
    connectCnt[sj] += 1

for j in range(m):
    if connectCnt[j] == 0:
        continue
    nx = int(xSum[j]/connectCnt[j])
    ny = int(ySum[j]/connectCnt[j])
    CD[j] = (nx, ny)
    XY[j+n] = (nx, ny)

dist_table = [[INF]*(n+m) for i in range(n+m)]
for i in range(n+m):
    for j in range(n+m):
        if i == j:
            continue
        x1, y1 = XY[j]
        dist = calc_energy(i, j)
        dist_table[i][j] = dist


s = calc_dist(path, dist_table)
score = round(10**9/(1000+math.sqrt(s)))
print(score, file=sys.stderr, flush=True)

for c, d in CD:
    print(c, d)

print(len(path))
for k in range(len(path)):
    r = path[k]
    if 0 <= r < n:
        print(1, r+1)
    else:
        print(2, r-n+1)
0