結果

問題 No.5007 Steiner Space Travel
ユーザー ra5anchorra5anchor
提出日時 2024-07-15 00:03:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 132 ms / 1,000 ms
コード長 5,524 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 78,016 KB
スコア 6,402,988
最終ジャッジ日時 2024-07-15 00:03:57
合計ジャッジ時間 5,692 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 106 ms
77,804 KB
testcase_01 AC 105 ms
77,684 KB
testcase_02 AC 106 ms
77,564 KB
testcase_03 AC 105 ms
77,708 KB
testcase_04 AC 132 ms
77,828 KB
testcase_05 AC 111 ms
77,448 KB
testcase_06 AC 104 ms
77,496 KB
testcase_07 AC 107 ms
77,856 KB
testcase_08 AC 105 ms
77,548 KB
testcase_09 AC 105 ms
77,448 KB
testcase_10 AC 108 ms
77,564 KB
testcase_11 AC 119 ms
77,456 KB
testcase_12 AC 112 ms
77,792 KB
testcase_13 AC 114 ms
77,848 KB
testcase_14 AC 111 ms
77,808 KB
testcase_15 AC 108 ms
77,680 KB
testcase_16 AC 110 ms
78,016 KB
testcase_17 AC 117 ms
77,820 KB
testcase_18 AC 107 ms
77,512 KB
testcase_19 AC 115 ms
77,596 KB
testcase_20 AC 108 ms
77,504 KB
testcase_21 AC 106 ms
77,764 KB
testcase_22 AC 108 ms
77,468 KB
testcase_23 AC 130 ms
77,812 KB
testcase_24 AC 108 ms
77,748 KB
testcase_25 AC 106 ms
77,792 KB
testcase_26 AC 116 ms
77,852 KB
testcase_27 AC 107 ms
77,600 KB
testcase_28 AC 105 ms
77,620 KB
testcase_29 AC 112 ms
77,664 KB
権限があれば一括ダウンロードができます

ソースコード

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):
    # 厳密解(HeldKarp), O(N^2 * 2^N)
    # dists[x][y]：xy間の距離

    N = len(dists)  # 都市数
    dp = [[10**18] * N for _ in range(2**N)]
    for i in range(N):
        # 地点0から最初の訪問地までの距離(スタートは地点0としている)
        dp[1<<i][i] = dists[0][i]
    for bit in range(1, 1<<N):
        for v in range(N):
            # 現在地vのビットが立っていない状態はスキップ
            if not bit & (1<<v):
                continue
            for nv in range(N):
                # 次の地点nvが訪問済みか、vからnvへ移動不可の場合はスキップ
                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])
    # 全地点訪問して地点0に戻る
    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))
# print(labels)
# print(stations)

# スタート地点のグループが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):
    # print(i, x, y)
    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) # 厳密解(HeldKarp)
# 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)) # リストから削除
tour.append((2, grp+1)) # type, id

for grp in tour_grp:
    stx, sty = stations[grp] # stationのx,y
    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)) # リストから削除
        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