結果
問題 | No.5007 Steiner Space Travel |
ユーザー | prussian_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 |
ソースコード
import randomfrom pathlib import Pathimport timeimport osimport mathLOCAL = Falsein_path = "./test"out_path = "./test/result"INF=10**20alpha = 5FILE_OUTPUT = Truedef 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_pointvisited = [False] * Nvisited[v] = Trueroute = [v]# 初期惑星以外のN-1個の惑星を訪問していくfor _ in range(N - 1):nearest_dist = INFnearest_v = -1# 一番近い惑星を探すfor next in range(N):if visited[next]:continued = dist(pos[v], pos[next])if d < nearest_dist:nearest_dist = dnearest_v = next# 次の頂点に移動v = nearest_vvisited[v] = Trueroute.append(nearest_v)return route#焼きなまし関数def simulated_annealing(score,temp):if score<=0:return Trueelif score/temp > 10:return Falsereturn 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 Falseab_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_cdreturn Trueelse: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 Falseabc_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_dereturn Trueelse:return False#3-optdef 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 Falsecost_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,fif (mode>>2)&1:B,C=C,Bif (mode>>1)&1:D,E=E,Dif mode&1:F,A=A,Fnew_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 Falseif (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_segmentreturn 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.costx_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 Trueelse: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]]=0success[mode[0]]=0while time.time()-dt<time_limit:temp = start_temp + (end_temp - start_temp) * (time.time()-dt)/time_limitrand = random.random()for mode in mode_ls:if rand<mode[1]:trial[mode[0]]+=1flag = mode[0](state,temp)if flag:success[mode[0]]+=1break#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 = 0for v,i,j in edge_list:if not i in point_ls:point_ls.add(i)count+=1if not j in point_ls:point_ls.add(j)count+=1if count >= limit:return point_lsdef 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=Nself.M=Mself.route = initial_route(pos,N)self.allocate = [-1]*Nself.pos = posself.center_pos = [[random.randint(0,1000),random.randint(0,1000)] for _ in range(M)]self.cost = self.calc_cost()#惑星iと惑星jの移動について、宇宙ステーションを用いた際の最適な距離とルートを返すdef calc_distance(self,i,j,output_path = False):path_candidate = [] #(distance,connector)#p1→p2d = dist(self.pos[i],self.pos[j])path_candidate.append((d,[]))#p1→m1→p2if 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→p2if 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→p2if 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 = 0for i in range(len(self.route)):cost += self.calc_distance(self.route[i-1],self.route[i])return costdef ans(self):res = []start_point = 0p1 = start_pointv1 = self.route.index(start_point)for _ in range(self.N):res.append(p1)v2 = (v1+1)%self.Np2 = self.route[v2]connector = self.calc_distance(p1,p2,output_path=True)for c in connector:res.append(c)v1 = v2p1 = p2res.append(p1)return resdef 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]*Mpoint_pos_sum = [[0,0] for _ in range(M)]for v in use_list:m = self.allocate[v]point_count[m]+=1point_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.costdef 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=0for _ in range(1):center_pos,ans,score = main(N,M,pos)if score>best_score:best_score = scorebest_pos = center_posbest_ans = ansoutput(best_pos,best_ans,score)