結果

問題 No.5007 Steiner Space Travel
ユーザー prussian_coderprussian_coder
提出日時 2023-04-27 21:09:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 916 ms / 1,000 ms
コード長 11,595 bytes
コンパイル時間 532 ms
コンパイル使用メモリ 87,252 KB
実行使用メモリ 97,064 KB
スコア 8,257,078
最終ジャッジ日時 2023-04-27 21:09:53
合計ジャッジ時間 30,121 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 895 ms
96,320 KB
testcase_01 AC 890 ms
96,972 KB
testcase_02 AC 894 ms
95,808 KB
testcase_03 AC 894 ms
96,196 KB
testcase_04 AC 891 ms
95,544 KB
testcase_05 AC 889 ms
95,216 KB
testcase_06 AC 907 ms
95,432 KB
testcase_07 AC 896 ms
93,656 KB
testcase_08 AC 892 ms
95,956 KB
testcase_09 AC 895 ms
94,364 KB
testcase_10 AC 899 ms
94,752 KB
testcase_11 AC 910 ms
93,900 KB
testcase_12 AC 896 ms
93,540 KB
testcase_13 AC 891 ms
95,524 KB
testcase_14 AC 905 ms
94,168 KB
testcase_15 AC 892 ms
95,424 KB
testcase_16 AC 907 ms
97,036 KB
testcase_17 AC 916 ms
96,132 KB
testcase_18 AC 895 ms
95,336 KB
testcase_19 AC 892 ms
94,520 KB
testcase_20 AC 895 ms
97,064 KB
testcase_21 AC 894 ms
96,632 KB
testcase_22 AC 900 ms
95,384 KB
testcase_23 AC 900 ms
95,524 KB
testcase_24 AC 915 ms
95,656 KB
testcase_25 AC 890 ms
95,200 KB
testcase_26 AC 899 ms
92,928 KB
testcase_27 AC 888 ms
95,636 KB
testcase_28 AC 893 ms
95,212 KB
testcase_29 AC 897 ms
93,004 KB
権限があれば一括ダウンロードができます

ソースコード

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

import random
from pathlib import Path
import time
import os
import math
LOCAL = False
in_path = "./test"
out_path = "./test/result"
INF=10**20
alpha = 5
FILE_OUTPUT = True
def read_data(file):
if LOCAL:
with open(file,mode="r") as f:
data = f.readlines()
N,M = map(int,data[0].split())
pos = [[int(x) for x in data[i+1].split()] for i in range(N)]
else:
N,M=map(int,input().split())
pos = [[int(x) for x in input().split()] for i in range(N)]
return N,M,pos
#2
def dist(p1,p2,a=alpha**2):
return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) * a
# Nearest Neighbour
def nearest_neighbor(pos,N):
start_point = random.randint(0,N-1) #
v = start_point
visited = [False] * N
visited[v] = True
route = [v]
# N-1
for _ in range(N - 1):
nearest_dist = INF
nearest_v = -1
#
for next in range(N):
if visited[next]:
continue
d = dist(pos[v], pos[next])
if d < nearest_dist:
nearest_dist = d
nearest_v = next
#
v = nearest_v
visited[v] = True
route.append(nearest_v)
return route
#
def simulated_annealing(score,temp):
if score<=0:
return True
elif score/temp > 10:
return False
return math.exp(-score/temp) > random.random()
#2-opt
def two_opt(state,temp):
#print("two-opt")
i = random.randint(1,state.N-2)
j = random.randint(1,state.N-2)
if i>j:
i,j=j,i
#(a,b)-(c,d)->(a,c)-(b-d)
a = state.route[i]
b = state.route[i+1]
c = state.route[j]
d = state.route[j+1]
if len(set({a,b,c,d}))!=4:
return False
ab_cd = state.calc_distance(a,b) + state.calc_distance(c,d)
ac_bd = state.calc_distance(a,c) + state.calc_distance(b,d)
if simulated_annealing(ac_bd-ab_cd,temp):
state.route[i+1:j+1] = state.route[i+1:j+1][::-1]
state.cost += ac_bd-ab_cd
return True
else:
return False
#
def point_insert(state,temp):
#print("Point_insert")
i = random.randint(1,state.N-2)
j = random.randint(1,state.N-2)
if i>j:
i,j=j,i
#(a,b,c)-(d,e)->(a,c)-(d,b,e)
a = state.route[i-1]
b = state.route[i]
c = state.route[i+1]
d = state.route[j]
e = state.route[j+1]
if len(set({a,b,c,d,e}))!=5:
return False
abc_de = state.calc_distance(a,b) + state.calc_distance(b,c) + state.calc_distance(d,e)
ac_dbe = state.calc_distance(a,c) + state.calc_distance(d,b) + state.calc_distance(b,e)
if simulated_annealing(ac_dbe-abc_de,temp):
state.route.remove(b)
if i<j:
state.route.insert(j,b)
else:
state.route.insert(j+1,b)
state.cost += ac_dbe-abc_de
return True
else:
return False
#3-opt
def three_opt(state,temp):
#print("three-opt")
i = random.randint(1,state.N-2)
j = random.randint(1,state.N-2)
k = random.randint(1,state.N-2)
i,j,k = sorted((i,j,k))
if abs(i-j)<=1 or abs(j-k)<=1:
return False
cost_list = []
a, b, c, d, e, f = state.route[i - 1], state.route[i], state.route[j - 1], state.route[j], state.route[k - 1], state.route[k % len(state.route)]
current_cost = state.calc_distance(a,b) + state.calc_distance(c,d) + state.calc_distance(e,f)
for mode in range(8):
A,B,C,D,E,F = a,b,c,d,e,f
if (mode>>2)&1:
B,C=C,B
if (mode>>1)&1:
D,E=E,D
if mode&1:
F,A=A,F
new_cost = state.calc_distance(A,B) + state.calc_distance(C,D) + state.calc_distance(E,F)
cost_list.append((new_cost-current_cost,mode))
cost_list.sort()
if cost_list[0][1]!=0:
next_mode = cost_list[0][1]
state.cost += cost_list[0][0]
elif simulated_annealing(cost_list[1][0],temp):
next_mode = cost_list[1][1]
state.cost += cost_list[1][0]
else:
return False
if (i - 1) < (k % len(state.route)):
first_segment = state.route[k% len(state.route):] + state.route[:i]
else:
first_segment = state.route[k % len(state.route):i]
second_segment = state.route[i:j]
third_segment = state.route[j:k]
if next_mode&1:
first_segment.reverse()
if (next_mode>>1)&1:
third_segment.reverse()
if (next_mode>>2)&1:
second_segment.reverse()
state.route = first_segment + second_segment + third_segment
return True
#
def move_station(state,temp):
move_range = int(temp/1000)
m = random.randint(0,state.M-1)
x,y = state.center_pos[m]
dx = random.randint(-move_range,move_range)
dy = random.randint(-move_range,move_range)
current_cost = state.cost
x_new = max(0,min(1000,x+dx))
y_new = max(0,min(1000,y+dy))
state.center_pos[m] = [x_new,y_new]
new_cost = state.calc_cost()
if simulated_annealing(new_cost-current_cost,temp):
return True
else:
state.center_pos[m]=[x,y]
#
def optimize_route(state,mode_ls,time_limit,start_temp,end_temp):
dt=time.time()
trial = dict()
success = dict()
for mode in mode_ls:
trial[mode[0]]=0
success[mode[0]]=0
while time.time()-dt<time_limit:
temp = start_temp + (end_temp - start_temp) * (time.time()-dt)/time_limit
rand = random.random()
for mode in mode_ls:
if rand<mode[1]:
trial[mode[0]]+=1
flag = mode[0](state,temp)
if flag:
success[mode[0]]+=1
break
#print(trial,success)
# O(N)
# limit:
def find_edge_point(state,limit):
edge_list = [(state.calc_distance(state.route[i-1],state.route[i]),state.route[i-1],state.route[i]) for i in range(len(state.route))]
edge_list.sort(reverse=True)
point_ls = set()
count = 0
for v,i,j in edge_list:
if not i in point_ls:
point_ls.add(i)
count+=1
if not j in point_ls:
point_ls.add(j)
count+=1
if count >= limit:
return point_ls
def K_means_clustering(state):
use_list = find_edge_point(state,30)
for _ in range(40):
state.find_nearest_station()
state.set_station(use_list)
class State:
def __init__(self,N,M,pos,initial_route):
self.N=N
self.M=M
self.route = initial_route(pos,N)
self.allocate = [-1]*N
self.pos = pos
self.center_pos = [[random.randint(0,1000),random.randint(0,1000)] for _ in range(M)]
self.cost = self.calc_cost()
#ij
def calc_distance(self,i,j,output_path = False):
path_candidate = [] #(distance,connector)
#p1→p2
d = dist(self.pos[i],self.pos[j])
path_candidate.append((d,[]))
#p1→m1→p2
if self.allocate[i]!=-1:
m1 = self.allocate[i]
d = dist(self.pos[i],self.center_pos[m1],a=alpha) + dist(self.pos[j],self.center_pos[m1],a=alpha)
path_candidate.append((d,[-m1-1]))
#p1→m2→p2
if self.allocate[j]!=-1:
m2 = self.allocate[j]
d = dist(self.pos[i],self.center_pos[m2],a=alpha) + dist(self.pos[j],self.center_pos[m2],a=alpha)
path_candidate.append((d,[-m2-1]))
#p1→m1→→m2→p2
if self.allocate[i]!=-1 and self.allocate[j]!=-1:
m1 = self.allocate[i]
m2 = self.allocate[j]
d = dist(self.pos[i],self.center_pos[m1],a=alpha) + dist(self.pos[j],self.center_pos[m2],a=alpha) + dist(self.center_pos[m1],self
                .center_pos[m2],a=1)
path_candidate.append((d,[-m1-1,-m2-1]))
path_candidate.sort()
if output_path:
return path_candidate[0][1]
else:
return path_candidate[0][0]
#1
def calc_cost(self):
cost = 0
for i in range(len(self.route)):
cost += self.calc_distance(self.route[i-1],self.route[i])
return cost
def ans(self):
res = []
start_point = 0
p1 = start_point
v1 = self.route.index(start_point)
for _ in range(self.N):
res.append(p1)
v2 = (v1+1)%self.N
p2 = self.route[v2]
connector = self.calc_distance(p1,p2,output_path=True)
for c in connector:
res.append(c)
v1 = v2
p1 = p2
res.append(p1)
return res
def find_nearest_station(self):
for i in range(self.N):
d = [dist(self.pos[i],self.center_pos[j]) for j in range(self.M)]
self.allocate[i] = d.index(min(d))
def set_station(self,use_list):
point_count = [0]*M
point_pos_sum = [[0,0] for _ in range(M)]
for v in use_list:
m = self.allocate[v]
point_count[m]+=1
point_pos_sum[m][0]+=self.pos[v][0]
point_pos_sum[m][1]+=self.pos[v][1]
for m in range(M):
if point_count[m]==0:
self.center_pos[m]=[random.randint(0,1000),random.randint(0,1000)]
else:
self.center_pos[m]=[point_pos_sum[m][0]//point_count[m],point_pos_sum[m][1]//point_count[m]]
def main(N,M,pos):
state = State(N,M,pos,nearest_neighbor)
mode_ls = [(two_opt,0.6),(three_opt,0.8),(point_insert,1)]
optimize_route(state,mode_ls,0.3,5000,1000)
K_means_clustering(state)
mode_ls = [(move_station,0.3),(two_opt,0.7),(three_opt,0.85),(point_insert,1)]
optimize_route(state,mode_ls,0.4,5000,1000)
return state.center_pos,state.ans(),state.cost
def output(center_pos,ans,score,file=""):
if LOCAL and FILE_OUTPUT:
Path(out_path).mkdir(exist_ok=True)
file_out = os.path.join(out_path,file.stem + "_" + str(int(score))+".txt")
with open(file_out,mode="w") as f:
for x,y in center_pos:
f.write(str(x)+" "+str(y)+"\n")
f.write(str(len(ans))+"\n")
for a in ans:
if a<0:
f.write("{0} {1}\n".format(2,-a))
else:
f.write("{0} {1}\n".format(1,a+1))
else:
for x,y in center_pos:
print(x,y)
print(len(ans))
for a in ans:
if a<0:
print(2,-a)
else:
print(1,a+1)
if LOCAL:
file_ls = Path(in_path).glob("*.txt")
for file in file_ls:
print(file)
N,M,pos = read_data(file)
center_pos,ans,score = main(N,M,pos)
output(center_pos,ans,score,file)
print(score)
else:
N,M,pos = read_data("")
best_score=0
for _ in range(1):
center_pos,ans,score = main(N,M,pos)
if score>best_score:
best_score = score
best_pos = center_pos
best_ans = ans
output(best_pos,best_ans,score)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0