結果

問題 No.5007 Steiner Space Travel
ユーザー ra5anchorra5anchor
提出日時 2024-07-15 01:09:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 917 ms / 1,000 ms
コード長 8,140 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 89,220 KB
スコア 7,863,309
最終ジャッジ日時 2024-07-15 01:09:32
合計ジャッジ時間 30,472 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 911 ms
87,940 KB
testcase_01 AC 911 ms
87,988 KB
testcase_02 AC 909 ms
87,824 KB
testcase_03 AC 911 ms
88,264 KB
testcase_04 AC 909 ms
88,056 KB
testcase_05 AC 909 ms
88,584 KB
testcase_06 AC 912 ms
88,176 KB
testcase_07 AC 911 ms
87,552 KB
testcase_08 AC 908 ms
89,220 KB
testcase_09 AC 909 ms
88,556 KB
testcase_10 AC 912 ms
87,792 KB
testcase_11 AC 910 ms
88,104 KB
testcase_12 AC 917 ms
88,400 KB
testcase_13 AC 912 ms
88,832 KB
testcase_14 AC 910 ms
87,848 KB
testcase_15 AC 915 ms
88,416 KB
testcase_16 AC 916 ms
88,064 KB
testcase_17 AC 909 ms
88,504 KB
testcase_18 AC 909 ms
88,404 KB
testcase_19 AC 911 ms
88,900 KB
testcase_20 AC 916 ms
88,212 KB
testcase_21 AC 911 ms
88,764 KB
testcase_22 AC 910 ms
88,472 KB
testcase_23 AC 909 ms
88,552 KB
testcase_24 AC 915 ms
88,160 KB
testcase_25 AC 908 ms
88,704 KB
testcase_26 AC 911 ms
88,336 KB
testcase_27 AC 915 ms
88,540 KB
testcase_28 AC 910 ms
88,476 KB
testcase_29 AC 910 ms
88,948 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import random
from time import perf_counter
import argparse
import sys
import math

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)

##############
def main(DEBUG):

    # ユークリッド距離
    def euclidean_distance(point1, point2):
        return sum((a - b) ** 2 for a, b in zip(point1, point2)) ** 0.5

    # K-meansクラスタリング
    def initialize_centroids(points, k):
        return random.sample(points, k)

    def assign_clusters(points, centroids):
        clusters = []
        for point in points:
            distances = [euclidean_distance(point, centroid) for centroid in centroids]
            cluster = distances.index(min(distances))
            clusters.append(cluster)
        return clusters

    def update_centroids(points, clusters, k):
        new_centroids = []
        for i in range(k):
            cluster_points = [points[j] for j in range(len(points)) if clusters[j] == i]
            if cluster_points:
                new_centroid = [sum(dim) / len(cluster_points) for dim in zip(*cluster_points)]
                new_centroids.append(tuple(new_centroid))
        return new_centroids

    def kmeans(points, k, max_iters=100):
        centroids = initialize_centroids(points, k)
        for _ in range(max_iters):
            clusters = assign_clusters(points, centroids)
            new_centroids = update_centroids(points, clusters, k)
            if centroids == new_centroids:
                break
            centroids = new_centroids
        return clusters, centroids


    def HeldKarp(dists):
        N = len(dists)
        dp = [[10**18] * N for _ in range(2**N)]
        for i in range(N):
            dp[1<<i][i] = dists[0][i]
        for bit in range(1, 1<<N):
            for v in range(N):
                if not bit & (1<<v):
                    continue
                for nv in range(N):
                    if bit & (1<<nv) or dists[v][nv] == -1:
                        continue
                    dp[bit | (1<<nv)][nv] = min(dp[bit | (1<<nv)][nv], dp[bit][v] + dists[v][nv])
        tot_dist = dp[(1<<N) - 1][0]

        now = 0
        tour = [now]
        visited_bit = (1 << N) - 1
        dist_sum = tot_dist
        EPS = 1e-5
        for _ in range(N-1):
            visited_bit ^= (1 << now)
            for last_city in range(N):
                if last_city == now:
                    continue
                if abs(dist_sum - dp[visited_bit][last_city] - dists[last_city][now]) < EPS:
                    break
            else:
                assert(False)
            dist_sum -= dists[last_city][now]
            now = last_city
            tour.append(now)
        return tot_dist, tour



    ########################
    tk = TimeKeeper()
    LIMIT = 0.8

    random.seed(0)
    ALPHA = 5 # 定数

    N, M = map(int, input().split())
    points = []
    for i in range(N):
        x, y = map(int, input().split())
        points.append((x, y))


    def solve(N, M, ALPHA, points):
        def calscore(stations, tour, ALPHA):
            s = 0
            NN = len(tour)
            for i in range(NN-1):
                type0, id0 = tour[i]
                type1, id1 = tour[i+1]
                id0 -= 1
                id1 -= 1
                if type0 == 1:
                    x0, y0 = id_to_xy[id0]
                else:
                    x0, y0 = stations[id0]
                if type1 == 1:
                    x1, y1 = id_to_xy[id1]
                else:
                    x1, y1 = stations[id1]
                d2 = (x0 - x1)**2 + (y0 - y1)**2
                if type0 + type1 == 2:
                    coef = ALPHA**2
                elif type0 + type1 == 3:
                    coef = ALPHA
                elif type0 + type1 == 4:
                    coef = 1
                s += d2 * coef
            sc = int(10**9 / (1000 + s**0.5) + 0.5)
            return sc

        # K-meansクラスタリングでM個のクラスに分類
        while True:
            labels, centroids = kmeans(points, M)
            stations = []
            for x, y in centroids:
                ix, iy = int(x+0.5), int(y+0.5)
                stations.append((ix, iy))
            if len(stations) == M:
                break

        # スタート地点のグループが0になるように回転
        stt = labels[0]
        labels = [(x-stt)%M for x in labels]
        for _ in range(stt):
            z = stations.pop(0)
            stations.append(z)

        # グループごとにp, stationの座標を
        # ps[i], stations[i]
        ps = [[] for _ in range(M)]
        id_to_xy = dict()
        for i, (x, y) in enumerate(points):
            ps[labels[i]].append((x, y, i))
            id_to_xy[i] = (x, y)
        # print(ps)

        # 最短巡回ルート
        dists = [[0]*M for _ in range(M)]
        for i in range(M):
            for j in range(M):
                dists[i][j] = euclidean_distance(stations[i], stations[j])
        tot_dist, tour_grp = HeldKarp(dists)

        # グループごとに解く
        tour = []
        grp = 0
        now = 0
        tour.append((1, now+1)) # type, id
        x, y = id_to_xy[now]
        ps[grp].remove((x, y, now)) # リストから削除

        for grp in tour_grp:
            stx, sty = stations[grp] # stationのx,y
            tour.append((2, grp+1)) # type, id
            while ps[grp]:
                mndist = 10**18
                for x, y, id in ps[grp]:
                    d = euclidean_distance(stations[grp], (x, y))
                    if d < mndist:
                        mndist = d
                        nxt = id
                tour.append((1, nxt+1))
                x, y = id_to_xy[nxt]
                ps[grp].remove((x, y, nxt)) # リストから削除

                nowx, nowy = x, y
                now = nxt
                while True:
                    # 最も近い地点とその距離を調べる
                    mndpp = 10**18
                    for x, y, id in ps[grp]:
                        d = euclidean_distance((nowx, nowy), (x, y))
                        if d < mndist:
                            mndpp = d
                            nxt = id
                    nxtx, nxty = id_to_xy[nxt]
                    d1 = euclidean_distance(stations[grp], (nowx, nowy))
                    d2 = euclidean_distance(stations[grp], (nxtx, nxty))
                    if ALPHA * mndpp < d1 + d2:
                        # 次の地点へ直接行く
                        tour.append((1, nxt+1))
                        ps[grp].remove((nxtx, nxty, nxt)) # リストから削除
                        nowx, nowy = nxtx, nxty
                        now = nxt
                    else:
                        break
                # ステーションに戻る
                tour.append((2, grp+1)) # type, id

        tour.append((2, 1))
        tour.append((1, 1))        

        sc = calscore(stations, tour, ALPHA)
        # print(sc, file=sys.stderr)
        return stations, tour, sc

    bestsc = 0
    loop = 0
    while True:
        # print(loop, file=sys.stderr)
        if tk.is_time_over(LIMIT):
            break

        ###########
        stations, tour, sc = solve(N, M, ALPHA, points)
        ###########

        if sc > bestsc:
            print('best', loop, sc, file=sys.stderr)
            bestsc = sc
            besttour = tour
            beststations = stations
        loop += 1

    # スコア
    print('SC', bestsc, file=sys.stderr)

    # 出力（ステーション）
    for x, y in beststations:
        print(x, y)
    # 出力（訪問箇所）
    print(len(besttour))
    for type, id in besttour:
        print(type, id)


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)
0