結果

問題 No.5007 Steiner Space Travel
ユーザー jakujaku12jakujaku12
提出日時 2023-05-02 16:05:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 976 ms / 1,000 ms
コード長 10,015 bytes
コンパイル時間 1,700 ms
コンパイル使用メモリ 87,292 KB
実行使用メモリ 84,492 KB
スコア 8,593,455
最終ジャッジ日時 2023-05-02 16:05:40
合計ジャッジ時間 32,764 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 976 ms
83,636 KB
testcase_01 AC 971 ms
83,616 KB
testcase_02 AC 971 ms
83,704 KB
testcase_03 AC 972 ms
83,048 KB
testcase_04 AC 975 ms
83,592 KB
testcase_05 AC 973 ms
83,728 KB
testcase_06 AC 973 ms
84,064 KB
testcase_07 AC 972 ms
83,352 KB
testcase_08 AC 973 ms
83,204 KB
testcase_09 AC 972 ms
84,232 KB
testcase_10 AC 976 ms
83,956 KB
testcase_11 AC 972 ms
84,080 KB
testcase_12 AC 971 ms
83,632 KB
testcase_13 AC 972 ms
84,492 KB
testcase_14 AC 974 ms
83,908 KB
testcase_15 AC 975 ms
83,380 KB
testcase_16 AC 975 ms
83,444 KB
testcase_17 AC 974 ms
83,756 KB
testcase_18 AC 976 ms
83,808 KB
testcase_19 AC 972 ms
83,644 KB
testcase_20 AC 969 ms
83,032 KB
testcase_21 AC 971 ms
84,228 KB
testcase_22 AC 970 ms
83,400 KB
testcase_23 AC 976 ms
83,684 KB
testcase_24 AC 972 ms
83,816 KB
testcase_25 AC 973 ms
83,168 KB
testcase_26 AC 974 ms
83,668 KB
testcase_27 AC 968 ms
83,844 KB
testcase_28 AC 970 ms
83,804 KB
testcase_29 AC 971 ms
83,788 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import permutations
import sys
from time import time
from random import random, randrange, choice, choices, randint
from heapq import heappop, heappush
from math import exp

START = time()
INF=10**9


def get_time(START):
    return time() - START

def dist(p1,p2):
    x1,y1=p1
    x2,y2=p2
    return (x1-x2)**2 + (y1-y2)**2

def dist2(p1,p2):
    return Ecost[p1][p2]


def cost(i: int, j: int):
    d = dist(Terminals[i], Terminals[j])
    if i<N: d*=5
    if j<N: d*=5
    return d

def calc(i: int, j: int, ans ):
    d = dist(Terminals[ans[i]], Terminals[ans[j]])
    if ans[i]<N: d*=5
    if ans[j]<N: d*=5
    return d

def dijkstra(s: int, g: int,mind: int):
    _dist = [INF] *(N+M)
    prev = [-1]*(N+M)

    que = [(0,s)]
    _dist[s]=0
    while que:
        d, v = heappop(que)
        if _dist[v] < d:
            continue
        if v==g:
            break
        for nv in range(T):
            nd = dist(Terminals[v],Terminals[nv])
            if v<N: nd*=5
            if nv<N: nd*=5
            nd += d
            # print(nv,nd,file = sys.stderr)s
            if nd < _dist[nv] and nd <= mind:
                prev[nv] = v
                _dist[nv] = nd
                heappush(que,(nd,nv))

    res=[]
    v = g
    while v!=s:
        res.append(v)
        v = prev[v]
    return res[::-1]



class KMEANS:

    def __init__(self):
        self.reps=[]
        self.dists=[]
        self.clusters=[]
        self.keep_flag=True

    # c_data: クラスタリング対象データ
    # k: クラスタ数
    def Clustering(self, c_datas, k):
        # 代表点を初期化
        self.RepInit(c_datas, k)

        while self.keep_flag:
            # 代表点と点の距離を計算
            self.ClusterDist(c_datas)
            # print(self.dists,file=sys.stderr)

            # 所属クラスタを更新
            self.ClusterUpdate()

            # 代表点を更新
            self.RepUpdate(c_datas)

    # クラスタ代表点の初期化 + 代表点と各点の距離と所属クラスタを格納するリストの初期化
    def RepInit(self, c_datas, k):
        self.reps = [(250,250),(500,250),(750,250),(750,500),(750,750),(500,750),(250,750),(250,500)]
        self.dists = [[-1 for j in range(k)] for i in range(len(c_datas))]
        self.clusters=[-1 for i in range(len(c_datas))]

    # 代表点と点の距離を計算
    def ClusterDist(self, c_datas):
        for (i, c_data) in enumerate(c_datas):
            for (j, rep) in enumerate(self.reps):
                # 各点の代表点との距離を計算
                self.dists[i][j] = dist(c_data, rep)

    # 所属クラスタ更新
    def ClusterUpdate(self):
        flag=False
        for (i, dist) in enumerate(self.dists):
            # クラスタ更新があった場合はwhileループのフラグをTrueに維持
            best_dist=INF
            best_v=-1
            for j,d in enumerate(dist):
                if d<best_dist:
                    best_dist = d
                    best_v = j
            if self.clusters[i] != best_v:
                flag=True
            # 距離のリストから最小値の引数を得る
            self.clusters[i] = best_v
        self.keep_flag=flag

     # クラスタの代表点を更新
    def RepUpdate(self, c_datas):
        for c_num in range(len(self.reps)):
            cluster_points=[]
            for i, (cluster, c_data) in enumerate(zip(self.clusters,c_datas)):
                if cluster == c_num:
                    # clauster_pointsにc_numクラスタの点を追加
                    cluster_points.append(c_data)
            if len(cluster_points) == 0:
                cluster_points.append((randint(0,1000),randint(0,1000)))
            # 点の平均を求め代表点を更新
            self.reps[c_num] = (sum([x for x,y in cluster_points])//len(cluster_points),sum([y for x,y in cluster_points])//len(cluster_points))
    

def calc_score(ans):
    score = 0
    for i in range(len(ans)-1):
        score += calc(i,i+1,ans)
    return score

def calc_score2(ans):
    score = 0
    for i in range(len(ans)-1):
        score += Ecost[ans[i]][ans[i+1]]
    return score


def probability(diff):
    start_temp=50
    end_temp=10
    temp = start_temp + (end_temp - start_temp) * get_time(START) / 0.85
    return exp(diff/temp)

def two_opt(tour):
    n = len(tour)
    improve = True
    while improve:
        improve = False
        for i in range(1, n-1):
            for j in range(i+1, n):
                    if i == 1 and j == n-1:
                        continue
                    delta = calc_delta_two(tour, i, j)
                    if delta > 0:
                        tour = reverse_path(tour, i, j-1)
                        improve = True
        return tour

def three_opt(tour):
    n = len(tour)
    improve = True
    while improve:
        improve = False
        for i in range(1, n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    if i == 1 and k == n-1:
                        continue
                    delta = calc_delta(tour, i, j, k)
                    if delta < 0:
                        tour = reverse_path(tour, i, j-1)
                        tour = reverse_path(tour, j, k-1)
                        tour = reverse_path(tour, i, k-1)
                        improve = True
        return tour

def two_opt_rand(tour):
    n = len(tour)
    a,b=randint(1,n-1),randint(1,n-1)
    while a==b or (a == 1 and b == n-1) or (b == 1 and a == n-1):
        a,b=randint(1,n-1),randint(1,n-1)
    if a>b:
        a,b=b,a
    delta = calc_delta_two(tour, a, b)
    if delta > 0:
        tour = reverse_path(tour, a, b-1)
    return tour

def three_opt(tour):
    n = len(tour)
    improve = True
    while improve:
        improve = False
        for i in range(1, n-2):
            for j in range(i+1, n-1):
                for k in range(j+1, n):
                    if i == 1 and k == n-1:
                        continue
                    delta = calc_delta(tour, i, j, k)
                    if delta < 0:
                        tour = reverse_path(tour, i, j-1)
                        tour = reverse_path(tour, j, k-1)
                        tour = reverse_path(tour, i, k-1)
                        improve = True
        return tour



def calc_delta_two(tour, i, j):
    a, b, c, d = tour[i-1], tour[i], tour[j-1], tour[j%len(tour)]
    return (dist2(a,b) + dist2(c,d)) - (dist2(a,c) + dist2(b,d))

def calc_delta(tour, i, j, k):
    a, b, c, d, e, f = tour[i-1], tour[i], tour[j-1], tour[j], tour[k-1], tour[k%len(tour)]
    return (dist2(a,b) + dist2(c,d) + dist2(e,f)) - (dist2(a,d) + dist2(c,e) + dist2(b,f))

def reverse_path(tour, i, j):
    return tour[:i] + tour[i:j+1][::-1] + tour[j+1:]



# インプット
N,M=map(int,input().split())
Terminals = [tuple(map(int,input().split())) for _ in range(N)]
KM=KMEANS()
KM.Clustering(Terminals,M)
Stations = KM.reps[:]
# print(Stations,file= sys.stderr)
Terminals += Stations
T=len(Terminals)
#各Terminalの移動コストをワーシャルフロイトで計算
Ecost=[[INF]*T for i in range(T)]
for i,t1 in enumerate(Terminals):
    for j,t2 in enumerate(Terminals):
        Ecost[i][j]=cost(i,j)
#ワーシャルフロイト
for k in range(T):
    for i in range(T):
        for j in range(T):
            Ecost[i][j]=min(Ecost[i][j],Ecost[i][k]+Ecost[k][j])

#ステーションを回る順序を全探索で決定
#ステーション毎に貪欲に回る順序を決定
StationCluster=[[] for i in range(M)]
TerminalsStation=[0]*N
for i in range(N):
    best_dist=INF
    best_st=-1
    for j in range(M):
        d = dist(Terminals[i],Terminals[j+N])
        if d<best_dist:
            best_dist=d
            best_st=j
    assert best_st!=-1
    StationCluster[best_st].append(i)
    TerminalsStation[i]=best_st
best_dist = INF
best_per = []
for per in permutations(range(M-1),M-1):
    station_list=[TerminalsStation[0]+N]
    for s in per:
        if s>=TerminalsStation[0]:s+=1
        station_list.append(s+N)
    station_list.append(TerminalsStation[0]+N)
    d = calc_score2(station_list)
    if d<best_dist:
        best_dist=d
        best_per=station_list[:]
# print(best_per,file=sys.stderr)        


        


ans = [0]
for i in range(M):
    for v in StationCluster[best_per[i]-N]:
        if v==0:
            continue
        ans.append(v)
ans.append(0)
print(ans, file = sys.stderr)

ans = two_opt(ans)
print(ans, file = sys.stderr)
# print(StationCluster, file = sys.stderr)

Tind=[0]*N
Tinv=[0]*N
for i,x in enumerate(ans[:N]):
    Tind[x]=i
    Tinv[i]=x

# 山登り
n = len(ans)
loop_cnt = 0
update_cnt=0        
best_score = calc_score2(ans)
dx=(10,-10,0,0,5,5,-5,-5)
dy=(0,0,10,-10,5,-5,5,-5)
# print(get_time(START),file=sys.stderr)
while get_time(START) < 0.80:
    loop_cnt+=1
    ans=two_opt_rand(ans)




# アウトプット
ans.append(0)
output=[0]
for i in range(len(ans)-1):
    output+=dijkstra(ans[i],ans[i+1],Ecost[ans[i]][ans[i+1]])
loopcnt2=0
while get_time(START)<0.87:
    loopcnt2+=1
    v = randrange(N,N+M)
    original = Terminals[v][:]
    best_i = -1
    sub_best_score = best_score
    for i in range(8):
        Terminals[v] = (original[0]+dx[i],original[1]+dy[i])
        current_score = calc_score(output)
        if current_score < sub_best_score:
            sub_best_score = current_score
            best_i = i

    if best_i != -1:
        best_score = sub_best_score
        Terminals[v] = (original[0]+dx[best_i], original[1]+dy[best_i])
        #print("move",best_score, file=sys.stderr)
    else:
        Terminals[v]=original[:]
for pos in Terminals[N:]:
    print(*pos)
print(len(output))
for v in output:
    if v<N:
        print(1,v+1)
    else:
        print(2,v+1-N)

print("Score", 10**9//(1000+calc_score(output)**0.5), file=sys.stderr)
print("Loop", loop_cnt, loopcnt2, update_cnt, file=sys.stderr)
print("time:",get_time(START) * 1000, file=sys.stderr)
0