結果

問題 No.5007 Steiner Space Travel
ユーザー rosso01rosso01
提出日時 2022-08-01 07:58:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 904 ms / 1,000 ms
コード長 5,199 bytes
コンパイル時間 715 ms
実行使用メモリ 88,204 KB
スコア 7,811,247
最終ジャッジ日時 2022-08-01 07:59:23
合計ジャッジ時間 29,779 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 897 ms
87,456 KB
testcase_01 AC 893 ms
87,496 KB
testcase_02 AC 895 ms
88,204 KB
testcase_03 AC 892 ms
87,220 KB
testcase_04 AC 894 ms
86,980 KB
testcase_05 AC 896 ms
87,440 KB
testcase_06 AC 893 ms
87,192 KB
testcase_07 AC 894 ms
87,060 KB
testcase_08 AC 894 ms
86,540 KB
testcase_09 AC 894 ms
87,996 KB
testcase_10 AC 895 ms
87,484 KB
testcase_11 AC 896 ms
86,596 KB
testcase_12 AC 896 ms
86,956 KB
testcase_13 AC 894 ms
87,724 KB
testcase_14 AC 895 ms
86,948 KB
testcase_15 AC 892 ms
87,980 KB
testcase_16 AC 893 ms
87,200 KB
testcase_17 AC 894 ms
86,888 KB
testcase_18 AC 892 ms
87,024 KB
testcase_19 AC 892 ms
86,904 KB
testcase_20 AC 894 ms
87,432 KB
testcase_21 AC 892 ms
86,972 KB
testcase_22 AC 892 ms
86,564 KB
testcase_23 AC 895 ms
87,152 KB
testcase_24 AC 903 ms
87,152 KB
testcase_25 AC 894 ms
86,588 KB
testcase_26 AC 892 ms
87,188 KB
testcase_27 AC 904 ms
87,256 KB
testcase_28 AC 893 ms
87,288 KB
testcase_29 AC 893 ms
86,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
②の山登りを焼きなましに変更

①ランダムにステーションを配置して各惑星から最も近いステーションまでのコストの和が最小になる解を山登りで見つける
②次に２点swapでコストの和が最小になる道順を時間いっぱいまで山登りで探索
"""

from random import randint,shuffle,sample,random
from time import time
from math import exp

# ダイクストラ（惑星専用）
def dijkstra(start = 0, INF=10**20):
    from heapq import heappop, heappush
    d = [INF for i in range(len(G))]
    prev = [-1]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        d_, v = heappop(que)
        if d[v] < d_: continue
        for u, c in G[v].items():
            if d[u] > d[v] + c:
                d[u] = d[v] + c
                prev[u] = v
                heappush(que, (d[u], u))
    return d,prev
  
# sからtまでの最短経路を復元
def recover_path(s,t):
  prev = PREV[s]
  path = [t]
  while prev[t] != -1:
    t = prev[t]
    path.append(t)
  return path[::-1]

# 道順を与えられたときに距離を返す
def calc_score(path):
  assert len(path) == N+1, "The length of path should be N+1"
  score = 0
  for i in range(N):
    score += D[path[i]][path[i+1]]
  return score

stime = time()
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
AB2 = {}
for a,b in AB:
  if a not in AB2:
    AB2[a] = set()
  AB2[a].add(b)
alpha = 5

CD = []
for i in range(M):
  c,d = randint(0,999),randint(0,999)
  while c in AB2 and d in AB2[c]:
    c,d = randint(0,999),randint(0,999)
  CD.append((c,d))
    
res = 0
for a,b in AB:
  MIN = 10**20
  for c,d in CD:
    MIN = min(MIN,(c-a)**2+(d-b)**2)
  res += MIN

res2 = res
for itr in range(10000):
  idx = randint(0,M-1)
  c2,d2 = randint(0,999),randint(0,999)
  while c2 in AB2 and d2 in AB2[c2]:
    c2,d2 = randint(0,999),randint(0,999)
    
  c0,d0 = CD[idx]
  CD[idx] = c2,d2

  res = 0
  for a,b in AB:
    MIN = 10**20
    for c,d in CD:
      MIN = min(MIN,(c-a)**2+(d-b)**2)
    res += MIN
    
  if res < res2:
    res2 = res
    
  else:
    CD[idx] = c0,d0
    
#print(time()-stime,res2)

G = [{} for _ in range(N+M)]
for i in range(N+M-1):
  if i < N:
    x1,y1 = AB[i]
  else:
    x1,y1 = CD[i-N]
  for j in range(i+1,N+M):
    if j < N:
      x2,y2 = AB[j]
    else:
      x2,y2 = CD[j-N]
    
    dist = (x2-x1)**2 + (y2-y1)**2
    if i<N and j<N:
      dist *= alpha**2
    elif i<N or j<N:
      dist *= alpha
      
    G[i][j] = G[j][i] = dist
    
D = [[0]*(N+M) for _ in range(N+M)]
PREV = [[-1]*(N+M) for _ in range(N+M)]
for i in range(N+M):
  D[i],PREV[i] = dijkstra(i)
  
ans = list(range(1,N))
score = calc_score([0]+ans+[0])

# 初期解
for i in range(100):
  ans2 = ans[:]
  shuffle(ans2)
  score2 = calc_score([0]+ans2+[0])
  
  if score2 < score:
    score = score2
    ans = ans2
    
    #print(score)
    
# 2点swapで山登り
time1 = time()
T0 = 20000
T1 = 0
exit_time = 0.8
deltaT = (T0-T1)/(exit_time - time1)
for itr in range(10**7):
  time2 = time()
  if time2 - stime > exit_time:
    break
  Tnow = T0 - (time2-time1)*deltaT
  i,j = sample(range(N-1),2)
  ans[i],ans[j] = ans[j],ans[i]
  
  score2 = calc_score([0]+ans+[0])
  
  delta = score - score2
  if delta >= 0 or random() < exp(delta/Tnow):
    score = score2
    
  else:
    ans[i],ans[j] = ans[j],ans[i]

ans = [0]+ans+[0]
all_path = [ans[0]]
for i in range(N):
  s,t = ans[i],ans[i+1]
  path = recover_path(s,t)
  for j in range(len(path)-1):
    all_path.append(path[j+1])
    
# 惑星->惑星の各枝について、途中でステーションを経由したした方がコストが減る場合は変更
all_path2 = [0]
for i in range(len(all_path)-1):
  a,b = all_path[i],all_path[i+1]
  if a >= N or b >= N:
    all_path2.append(b)
    continue
  MIN = D[a][b]
  argmin = -1
  for j in range(N,N+M):
    if D[a][j] + D[j][b] < MIN:
      MIN = D[a][j] + D[j][b]
      argmin = j
      
  if argmin != -1:
    all_path2.append(j)
  all_path2.append(b)
    
# 一度も訪問しないステーションが発生した場合は一番近いステーションから往復する
unvisited = set(i for i in range(N+M)) - set(all_path)
#unvisited = set([N])
if unvisited:
  for x in unvisited:
    MIN = 10**20
    argmin = -1
    for y in range(N,N+M):
      if x == y:
        continue
      if D[x][y] < MIN:
        MIN = D[x][y]
        argmin = y
        
    idx = all_path.index(y)
    all_path.insert(idx+1,y)
    all_path.insert(idx+1,x)
    
# 各ステーションを重心に移動させる
data = {i:set() for i in range(M)}
for i in range(len(all_path)-1):
  a,b = all_path[i],all_path[i+1]
  if a<N and b<N:
    continue
  if a>=N and b>=N:
    continue
  if a > b:
    a,b = b,a
  data[b-N].add(a)
  
#print(data)
  
for i in range(M):
  X = []
  Y = []
  for j in data[i]:
    X.append(AB[j][0])
    Y.append(AB[j][1])
  #assert X
  
  if X:
    CD[i] = sum(X)//len(X),sum(Y)//len(Y)
    
#print(score)
#print(all_path)
for c,d in CD:
  print(c,d)
print(len(all_path))
for idx in all_path:
  if idx < N:
    t = 1
  else:
    t = 2
    idx -= N
    
  print(t,idx+1)
0