結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー LyricalMaestro
提出日時 2024-02-26 02:01:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 139 ms / 1,000 ms
コード長 4,312 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 77,492 KB
スコア 6,154,107
最終ジャッジ日時 2024-02-26 02:01:22
合計ジャッジ時間 5,128 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 solve(N, M, planets):
    """
    旅行の順番を貪欲法+シミュレーテッドアニーリングで求める
    """
    random.seed(10)

    # stationの情報の格納
    stations = []
    for i in range(M):
        stations.append(planets[i])

    # distance-matrixの計算
    energy_cost_matrix = [[0] * N  for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            x1, y1 = planets[i]
            x2, y2 = planets[j]
            energy_cost_matrix[i][j] = (x1 - x2)**2 + (y1 - y2)**2
            energy_cost_matrix[i][j] *= ALPHA ** 2
    
    # 貪欲法で初期解の生成
    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 = [(1, i + 1) for i in travel_seq]

    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()
0