結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2024-03-03 03:58:21 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 189 ms / 1,000 ms |
| コード長 | 7,125 bytes |
| コンパイル時間 | 302 ms |
| コンパイル使用メモリ | 81,572 KB |
| 実行使用メモリ | 77,852 KB |
| スコア | 7,977,999 |
| 最終ジャッジ日時 | 2024-03-03 03:58:28 |
| 合計ジャッジ時間 | 7,362 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
import math
import sys
import random
ALPHA = 5
class Result:
def __init__(self, stations, travel_seq):
self.stations = []
for x, y in stations:
self.stations.append(f"{x} {y}")
self.travel_seq = []
for t, r in travel_seq:
self.travel_seq.append(f"{t} {r}")
def calc_score(stations, travel_seq, planets):
# スコア計算
S = 0
for i in range(len(travel_seq) - 1):
t1, r1 = travel_seq[i]
t2, r2 = travel_seq[i + 1]
if t1 == 2 and t2 == 2:
x1, y1 = stations[r1 - 1]
x2, y2 = stations[r2 - 1]
S += ((x1 - x2) ** 2 + (y1 - y2) ** 2)
elif t1 == 2 and t2 == 1:
x1, y1 = stations[r1 - 1]
x2, y2 = planets[r2 - 1]
S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
elif t1 == 1 and t2 == 2:
x1, y1 = planets[r1 - 1]
x2, y2 = stations[r2 - 1]
S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
else:
# t1 == 1 and t2 == 1
alpha2 = ALPHA ** 2
x1, y1 = planets[r1 - 1]
x2, y2 = planets[r2 - 1]
S += alpha2 * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
print(f"S = {S}", file=sys.stderr, flush=True)
score = (10 ** 9) / (1000 + math.sqrt(S))
score = int(score)
print(f"score = {score}", file=sys.stderr, flush=True)
def k_means(planets, M):
cluser_array = [-1] * len(planets)
for i in range(len(planets)):
cluster_index = random.randint(0, M - 1)
cluser_array[i] = cluster_index
ave_x = 0.0
ave_y = 0.0
for x, y in planets:
ave_x += x
ave_y += y
ave_x /= len(planets)
ave_y /= len(planets)
for _ in range(100):
# Mステップ
averages_x = [0] * M
averages_y = [0] * M
counts = [0] * M
for i, cluster_index in enumerate(cluser_array):
averages_x[cluster_index] += planets[i][0]
averages_y[cluster_index] += planets[i][1]
counts[cluster_index] += 1
for i in range(M):
if counts[i] > 0:
averages_x[i] /= counts[i]
averages_y[i] /= counts[i]
else:
averages_x[i] = ave_x
averages_y[i] = ave_y
# Eステップ
for i, planet in enumerate(planets):
min_distance = float("inf")
min_cluster_index = -1
for j in range(M):
distance = (planet[0] - averages_x[j]) ** 2 + (planet[1] - averages_y[j]) ** 2
if distance < min_distance:
min_distance = distance
min_cluster_index = j
cluser_array[i] = min_cluster_index
stations = []
for i in range(M):
stations.append((int(averages_x[i]), int(averages_y[i])))
return stations
def solve(N, M, planets):
"""
K-meansでstationの位置を最適化する
旅行の順番を貪欲法+シミュレーテッドアニーリングで求める
"""
random.seed(10)
# K-meansによるstationの情報の格納
stations = k_means(planets, M)
# distance-matrixの計算
energy_cost_matrix = [[float("inf") for _ in range(N + M)] for _ in range((N + M))]
for i in range(N + M):
for j in range(N + M):
if i == j:
energy_cost_matrix[i][j] = 0
continue
weight = 1
if i < N:
x1, y1 = planets[i]
weight *= ALPHA
else:
x1, y1 = stations[i - N]
if j < N:
x2, y2 = planets[j]
weight *= ALPHA
else:
x2, y2 = stations[j - N]
energy_cost_matrix[i][j] = (x1 - x2)**2 + (y1 - y2)**2
energy_cost_matrix[i][j] *= weight
# ワーシャルフロイド法で最短距離を求める
next_hop_matrix = [[i for _ in range(N + M)] for i in range((N + M))]
for k in range(N + M):
for i in range(N + M):
for j in range(N + M):
if energy_cost_matrix[i][j] > energy_cost_matrix[i][k] + energy_cost_matrix[k][j]:
energy_cost_matrix[i][j] = energy_cost_matrix[i][k] + energy_cost_matrix[k][j]
next_hop_matrix[i][j] = k
# 貪欲法で初期解の生成
travel_seq = [0]
last_pos = 0
passed = [False] * N
passed[0] = True
travel_cost = 0
for _ in range(N - 1):
base_cost = float("inf")
next_pos = -1
for j in range(N):
if passed[j]:
continue
cost = energy_cost_matrix[last_pos][j]
new_cost = travel_cost + cost
if new_cost < base_cost:
base_cost = new_cost
next_pos = j
travel_cost = base_cost
travel_seq.append(next_pos)
passed[next_pos] = True
last_pos = next_pos
cost = energy_cost_matrix[last_pos][0]
travel_cost += cost
travel_seq.append(0)
print(f"init_travel_cost: {travel_cost}", file=sys.stderr, flush=True)
# 山登り法で最適解を探す
for _ in range(10000):
i = random.randint(1, N - 1)
j = random.randint(1, N - 1)
if i == j:
continue
if i > j:
tmp = i
i = j
j = tmp
new_cost = travel_cost
new_cost -= energy_cost_matrix[travel_seq[i - 1]][travel_seq[i]]
new_cost -= energy_cost_matrix[travel_seq[j]][travel_seq[j + 1]]
new_cost += energy_cost_matrix[travel_seq[i - 1]][travel_seq[j]]
new_cost += energy_cost_matrix[travel_seq[i]][travel_seq[j + 1]]
if new_cost < travel_cost:
travel_cost = new_cost
for k in range(i, (i + j + 1) // 2):
tmp = travel_seq[k]
travel_seq[k] = travel_seq[j + i - k]
travel_seq[j + i - k] = tmp
print(f"travel_cost: {travel_cost}", file=sys.stderr, flush=True)
new_travel_seq = []
new_travel_seq.append((1, travel_seq[0] + 1))
for i in range(len(travel_seq) - 1):
i0 = travel_seq[i]
j0 = travel_seq[i + 1]
cur = j0
path = []
while cur != i0:
path.append(cur)
cur = next_hop_matrix[i0][cur]
path.reverse()
for p in path:
if p < N:
new_travel_seq.append((1, p + 1))
else:
new_travel_seq.append((2, p - N + 1))
calc_score(stations, new_travel_seq, planets)
return Result(stations, new_travel_seq)
def main():
N, M = map(int, input().split())
planets = []
for _ in range(N):
a, b = map(int, input().split())
planets.append((a, b))
result = solve(N, M, planets)
for i in range(M):
print(result.stations[i])
print(len(result.travel_seq))
for i in range(len(result.travel_seq)):
print(result.travel_seq[i])
if __name__ == "__main__":
main()