結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー ra5anchor
提出日時 2024-07-15 00:33:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 185 ms / 1,000 ms
コード長 5,834 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 78,440 KB
スコア 7,471,823
最終ジャッジ日時 2024-07-15 00:33:41
合計ジャッジ時間 6,301 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import sys

# ユークリッド距離
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

##############
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))

# K-meansクラスタリングでM個のクラスに分類
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))

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

# グループごとに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)
# print(tour_grp) [0, 2, 5, 3, 1, 7, 4, 6]とか

# グループごとに解く
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))        

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

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

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