結果

問題 No.5007 Steiner Space Travel
ユーザー LyricalMaestroLyricalMaestro
提出日時 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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 189 ms
77,712 KB
testcase_01 AC 158 ms
77,724 KB
testcase_02 AC 158 ms
77,720 KB
testcase_03 AC 170 ms
77,724 KB
testcase_04 AC 172 ms
77,852 KB
testcase_05 AC 159 ms
77,724 KB
testcase_06 AC 159 ms
77,720 KB
testcase_07 AC 159 ms
77,720 KB
testcase_08 AC 170 ms
77,724 KB
testcase_09 AC 158 ms
77,724 KB
testcase_10 AC 158 ms
77,720 KB
testcase_11 AC 158 ms
77,712 KB
testcase_12 AC 161 ms
77,720 KB
testcase_13 AC 158 ms
77,720 KB
testcase_14 AC 169 ms
77,724 KB
testcase_15 AC 160 ms
77,724 KB
testcase_16 AC 170 ms
77,720 KB
testcase_17 AC 170 ms
77,712 KB
testcase_18 AC 162 ms
77,720 KB
testcase_19 AC 160 ms
77,724 KB
testcase_20 AC 157 ms
77,720 KB
testcase_21 AC 158 ms
77,724 KB
testcase_22 AC 157 ms
77,724 KB
testcase_23 AC 169 ms
77,724 KB
testcase_24 AC 159 ms
77,716 KB
testcase_25 AC 169 ms
77,720 KB
testcase_26 AC 170 ms
77,724 KB
testcase_27 AC 158 ms
77,720 KB
testcase_28 AC 159 ms
77,724 KB
testcase_29 AC 169 ms
77,712 KB
権限があれば一括ダウンロードができます

ソースコード

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