結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2023-04-26 15:57:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 706 ms / 1,000 ms |
| コード長 | 14,029 bytes |
| コンパイル時間 | 365 ms |
| コンパイル使用メモリ | 86,916 KB |
| 実行使用メモリ | 92,240 KB |
| スコア | 8,233,695 |
| 最終ジャッジ日時 | 2023-04-26 15:58:21 |
| 合計ジャッジ時間 | 24,097 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#from matplotlib import pyplot as plt
def visualize(N,M,pos,center_pos,allocate):
fig = plt.figure(figsize=(10,10))
for i in range(N):
plt.plot(pos[i][0],pos[i][1],color=color_ls[allocate[i]],marker=".")
for i in range(M):
plt.plot(center_pos[i][0],center_pos[i][1],color=color_ls[i],marker="*")
plt.show()
plt.close()
INF=10**20
alpha = 5
import random
from pathlib import Path
import time
LOCAL = False
in_path = "./test"
img_path = "./image"
color_ls = ["red","blue","green","orange","gray","pink","cyan","black"]
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
#中心点と各惑星の距離を全探索し、短い順に並びかえる
def calc_dist_from_center(N,M,center_pos,pos):
dist_list = []
for m in range(M):
for n in range(N):
d = dist(pos[n],center_pos[m])
dist_list.append((d,m,n))
return sorted(dist_list)
#中心点から近い惑星順にクラスわけする
def allocate_cluster(N,M,center_pos,pos):
dist_list = calc_dist_from_center(N,M,center_pos,pos)
allocate = [-1]*N
cluster_counts = [0]*M
total_count = 0
for d,m,n in dist_list:
if allocate[n]==-1:
allocate[n]=m
cluster_counts[m]+=1
total_count+=1
if total_count==N:
break
return allocate,cluster_counts
#クラスター分けされた点をもとに、k-means法に倣って中心点を算出する。
# グループカウントが多いものは中心点を2つにして、クラスターを分ける。
def calc_center(N,M,pos,allocate,cluster_counts,weight=None,max_size = 15,split_mode = True):
if weight is None:
weight = [1]*N
point_sums = [[0,0] for _ in range(M)]
point_counts = [0]*M
for i in range(N):
m=allocate[i]
point_sums[m][0]+=pos[i][0]*weight[i]
point_sums[m][1]+=pos[i][1]*weight[i]
point_counts[m]+=weight[i]
center_pos = []
#clsuter_countが大きい順に見ていき、中心点がM個を超えたら中断する
if split_mode:
order = sorted([(cluster_counts[i],i) for i in range(M)],reverse=True)
else:
order = [(cluster_counts[i],i) for i in range(M)]
for _,m in order:
if cluster_counts[m]==0:
center_pos.append([random.randint(0,1000),random.randint(0,1000)])
else:
x = int(point_sums[m][0]/point_counts[m])
y = int(point_sums[m][1]/point_counts[m])
center_pos.append([x,y])
if cluster_counts[m]>=max_size and split_mode:
dx = random.randint(-20,20)
dy = random.randint(-20,20)
while not (0<=x+dx<=1000 and 0<y+dy<=1000):
dx = random.randint(-5,5)
dy = random.randint(-5,5)
center_pos.append([x+dx,y+dy])
if len(center_pos)==M:
break
return center_pos
def calc_clustering_distance(center_pos,allocate,pos):
total_dist = 0
for i in range(len(pos)):
m = allocate[i]
total_dist += dist(pos[i],center_pos[m])
return total_dist
#K-means法に倣って惑星の点をグループ分けする
def clustering(N,M,pos,max_size,weight = None):
if weight is None:
weight = [1]*N
center_pos = [[random.randint(0,1000),random.randint(0,1000)] for _ in range(M)] #ランダム初期化
allocate,cluster_counts= allocate_cluster(N,M,center_pos,pos)
loop = 0
while True:
center_pos = calc_center(N,M,pos,allocate,cluster_counts,max_size=max_size,weight = weight)
allocate,cluster_counts = allocate_cluster(N,M,center_pos,pos)
#print(loop,cluster_counts)
if loop>=10 and max(cluster_counts)<=max_size:
break
loop+=1
center_pos = calc_center(N,M,pos,allocate,cluster_counts,weight = weight,split_mode=False)
cluster_dist = calc_clustering_distance(center_pos,allocate,pos)
#visualize(N,M,pos,center_pos,allocate)
return center_pos,allocate,cluster_dist
def f(S,x,n):
return S*(n+1)+x
#クラスター内にてBitDPでTSPを解く O(n^2*2^n)
def tsp(id_list,pos,center_pos):
#point 0~n-1が惑星、nが中心点
n=len(id_list)-1
dp = [INF]*(n+1)*(1<<n)
dp[f(0,n,n)]=0
for S in range(1<<n):
for s in range(n+1):
if dp[f(S,s,n)]==INF:
continue
for t in range(n):
if (S>>t)&1:
continue
S2 = S|(1<<t)
if s!=n:
dp[f(S2,t,n)]=min(dp[f(S,s,n)] + dist(pos[id_list[s]],pos[id_list[t]]),dp[f(S2,t,n)])
else:
dp[f(S2,t,n)]=min(dp[f(S,s,n)] + dist(center_pos,pos[id_list[t]],a=alpha),dp[f(S2,t,n)])
dp[f(S2,n,n)]=min(dp[f(S2,t,n)] + dist(center_pos,pos[id_list[t]],a=alpha),dp[f(S2,n,n)])
#BitDPから復元
path_list = []
route = []
state = (1<<n)-1
now = n
v = dp[-1]
e = 10**(-5)
while state != 0 or now !=n:
found = False
if now == n:
for t in range(n):
d = dist(center_pos,pos[id_list[t]],a=alpha)
if dp[f(state,t,n)]==INF:
continue
if v - dp[f(state,t,n)] >= d - e:
if t!=n:
route.append(id_list[t])
else:
path_list.append(route)
route = []
now = t
v -= d
found = True
break
else:
state = state ^ (1<<now)
for t in range(n+1):
if dp[f(state,t,n)]==INF:
continue
if t!=n:
if not (state>>t)&1:
continue
d = dist(pos[id_list[now]],pos[id_list[t]])
else:
d = dist(pos[id_list[now]],center_pos,a=alpha)
if v - dp[f(state,t,n)] >= d - e:
if t!=n:
route.append(id_list[t])
else:
path_list.append(route)
route = []
now = t
v -= d
found=True
break
return path_list
def tsp_between_space(M,center_pos):
n = M
dp = [[INF for _ in range(n)] for _ in range(1<<n)]
dp[0][-1]=0
for S in range(1<<n):
for s in range(n):
if dp[S][s]==INF:
continue
for t in range(n):
if (S>>t)&1:
continue
S2 = S|(1<<t)
d = dist(center_pos[s],center_pos[t],a=1)
dp[S2][t]=min(dp[S][s] + d, dp[S2][t])
#BitDPから復元
state = (1<<n)-1
s = n-1
path_list = [s]
v = dp[-1][-1]
e = 10**(-5)
while state != 0:
state ^=(1<<s)
for t in range(n):
if not (state>>t)&1:
continue
if dp[state][t]==INF:
continue
d = dist(center_pos[s],center_pos[t],a=1)
if v - dp[state][t] >= d - e:
path_list.append(t)
s = t
v -= d
break
return path_list
def adjust_center_pos(path,pos,M):
L=len(path)
edge_count = [0]*M
edge_x_sum = [0]*M
edge_y_sum = [0]*M
for i in range(L-1):
if path[i]<0 and path[i+1]>=0:
p,q = -path[i]-1,path[i+1]
edge_count[p]+=5
edge_x_sum[p]+=pos[q][0]*5
edge_y_sum[p]+=pos[q][1]*5
elif path[i]>=0 and path[i+1]<0:
p,q = -path[i+1]-1,path[i]
edge_count[p]+=5
edge_x_sum[p]+=pos[q][0]*5
edge_y_sum[p]+=pos[q][1]*5
elif path[i]<0 and path[i+1]<0:
p,q = -path[i]-1,-path[i+1]-1
edge_count[p]+=1
edge_count[q]+=1
edge_x_sum[p]+=pos[q][0]
edge_y_sum[p]+=pos[q][1]
edge_x_sum[q]+=pos[p][0]
edge_y_sum[q]+=pos[p][1]
center_pos = [[edge_x_sum[m]//edge_count[m],edge_y_sum[m]//edge_count[m]] for m in range(M)]
return center_pos
def calc_score(path,pos,center_pos):
score = 0
L = len(path)
cost_detail = {1:0,5:0,25:0}
for i in range(L-1):
a=1
if path[i]>=0:
p1 = pos[path[i]]
a*=5
else:
p1 = center_pos[-path[i]-1]
if path[i+1]>=0:
p2 = pos[path[i+1]]
a*=5
else:
p2 = center_pos[-path[i+1]-1]
score += dist(p1,p2,a)
cost_detail[a]+=dist(p1,p2,a)
if LOCAL:
print(cost_detail)
return 10**9 / (1000 + score**0.5)
#クラスター内の経路について、前クラスタと最も近い接続点を一番前、後クラスタと最も近い点を一番後ろに持ってくる
def reorder_path(cluster_path,m,pos,prev_pos,next_pos):
prev_pos_min,next_pos_min = INF,INF
prev_best,next_best = [],[]
for l in cluster_path:
d = dist(prev_pos,pos[l[0]])
if d<prev_pos_min:
prev_pos_min=d
prev_best=l
d = dist(prev_pos,pos[l[0]])
if d<prev_pos_min:
prev_pos_min=d
prev_best=l[::-1]
for l in cluster_path:
if l==prev_best or l==prev_best[::-1]:
continue
d = dist(next_pos,pos[l[0]])
if d<next_pos_min:
next_pos_min=d
next_best=l[::-1]
d = dist(prev_pos,pos[l[0]])
if d<prev_pos_min:
next_pos_min=d
next_best=l
new_route = prev_best+[-m-1]
for a in cluster_path:
if a!=prev_best and a!=prev_best[::-1] and a!=next_best and a!=next_best[::-1]:
new_route+=a
new_route+=[-m-1]
new_route+=next_best
return new_route
def connect_cluster(p1,p2,m1,m2,m1_id,m2_id):
d1 = dist(p1,p2) #そのままつなぐ
d2 = dist(p1,m1,a=alpha) + dist(m1,p2,a=alpha) #m1を経由
d3 = dist(p1,m2,a=alpha) + dist(m2,p2,a=alpha) #m2を経由
d4 = dist(p1,m1,a=alpha) + dist(m1,m2,a=1) + dist(m2,p2,a=alpha) #両方を経由
d_min = min(d1,d2,d3,d4)
if d_min == d1:
return []
elif d_min == d2:
return [m1_id]
elif d_min == d3:
return [m2_id]
else:
return [m1_id,m2_id]
def main(N,M,pos):
#隣接する惑星間の最小距離を計算する
closest_dist = [INF]*N
for s in range(N):
for t in range(s+1,N):
d = dist(pos[s],pos[t])**2
closest_dist[s] = min(d,closest_dist[s])
closest_dist[t] = min(d,closest_dist[t])
#K-meansで8個に分割
best_dist = INF
for _ in range(10):
center_pos_temp,allocate_temp,cluster_dist = clustering(N,M,pos,50,weight = closest_dist)
if cluster_dist<best_dist:
best_dist = cluster_dist
center_pos = center_pos_temp
allocate = allocate_temp
ans = []
#クラスタ間での回る順番をTSPで決める
space_order = tsp_between_space(M,center_pos)
#クラスタ内で回る順番をTSPで決める
route = []
for im,m in enumerate(space_order):
id_list = [i for i in range(N) if allocate[i]==m]
n = len(id_list)
path_in_cluster = []
#サイズが小さい時は全部使う
if n<=12:
path_in_cluster += tsp(id_list+[-m-1],pos,center_pos[m])
#サイズが大きすぎる時は、clusteringで分割してそれぞれでTSP
else:
pos2 = [pos[i] for i in id_list]
blocks = n//10 + 1
_,allocate2,_ = clustering(n,blocks,pos2,12)
for i2 in range(blocks):
id_list2 = [id_list[i] for i in range(n) if allocate2[i]==i2]
path_in_cluster += tsp(id_list2+[-m-1],pos,center_pos[m])
prev_pos = center_pos[space_order[(im-1)%M]]
next_pos = center_pos[space_order[(im+1)%M]]
path_route = reorder_path(path_in_cluster,m,pos,prev_pos,next_pos)
route.append(path_route)
#クラスター間の接続
for i in range(M):
ans += route[i]
m1_id = space_order[i]
m2_id = space_order[(i+1)%M]
ans += connect_cluster(pos[route[i][-1]],pos[route[(i+1)%M][0]],center_pos[m1_id],center_pos[m2_id],-m1_id-1,-m2_id-1)
#初期位置を0にする
start_point = ans.index(0)
ans = ans[start_point:]+ans[:start_point+1] #初期解
#center-posの位置を補正（最小二乗法の要領）
center_pos = adjust_center_pos(ans,pos,M)
#scoreの計算
score = calc_score(ans,pos,center_pos)
return center_pos,ans,score
def output(center_pos,ans):
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)
M=8
center_pos,ans,score = main(N,M,pos)
output(center_pos,ans)
print(score)
else:
N,M,pos = read_data("")
best_score=0
for _ in range(2):
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)