結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー Akari
提出日時 2022-07-30 16:46:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 333 ms / 1,000 ms
コード長 2,470 bytes
コンパイル時間 65 ms
実行使用メモリ 86,396 KB
スコア 7,982,621
最終ジャッジ日時 2022-07-30 16:46:44
合計ジャッジ時間 12,010 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import numpy as np
from scipy.cluster.vq import kmeans2


def tsp(cost):
    n = cost.shape[0]
    n2 = 1 << n
    INF = 1 << 60
    dp = np.full((n2, n, 2), INF, np.int64)
    for i in range(n): dp[1 << i, i] = 0
    for i in range(n2):
        for j in range(n):
            if ~i >> j & 1: continue
            for k in range(n):
                if i >> k & 1: continue
                l = i | 1 << k
                d = dp[i, j, 0] + cost[j, k]
                if d < dp[l, k, 0]: dp[l, k] = d, j
    res = np.empty(n, np.int64)
    i = n2 - 1
    x = dp[i, :, 0].argmin()
    for j in range(n):
        res[j] = x
        p = dp[i, x, 1]
        i ^= 1 << x
        x = p
    return res

def greedy(cost):
    n = cost.shape[0]
    res = np.empty(n, np.int64)
    INF = 1 << 60
    d_min = INF
    visited = np.empty(n, np.bool_)
    tmp = np.empty(n, np.int64)
    for x in range(n):
        visited.fill(False)
        visited[x] = True
        tmp[0] = x
        d = 0
        for i in range(1, n):
            y = np.where(visited, INF, cost[x]).argmin()
            tmp[i] = y
            visited[y] = True
            d += cost[x, y]
            x = y
        if d < d_min: res = tmp.copy()
    return res




def main():
    np.random.seed(11)
    N, M = map(int, input().split())
    X, Y = np.fromstring(sys.stdin.read(), np.int64, sep=' ').reshape(-1, 2).T
    C, L = kmeans2(np.vstack((X, Y)).T.astype(np.float64), M, 20, minit='++')
    C = np.round_(C).astype(np.int64)
    sb2 = lambda x: np.subtract.outer(x, x) ** 2
    dist = lambda x, y: sb2(x) + sb2(y)
    for i in range(M): print(*C[i])
    ans = [[1, 1]]
    R = tsp(dist(C[:, 0], C[:, 1]))
    c0 = ((C[:, 0] - X[0]) ** 2 + (C[:, 1] - Y[0]) ** 2).argmin()
    R = np.roll(R, -(R == c0).nonzero()[0][0])
    for i in R:
        ans.append([2, i + 1])
        cx, cy = C[i]
        idx = L == i
        V = idx.nonzero()[0]
        n = V.shape[0]
        cost = dist(X[idx], Y[idx])
        cost0 = (X[idx] - cx) ** 2 + (Y[idx] - cy) ** 2
        U = tsp(cost) if n < 11 else greedy(cost)
        u = U[0]
        ans.append([1, V[u] + 1])
        for nu in U[1:]:
            if 5 * cost[u, nu] > cost0[u] + cost0[nu]: ans.append([2, i + 1])
            ans.append([1, V[nu] + 1])
            u = nu
        ans.append([2, i + 1])
    ans.append([2, R[0] + 1])
    ans.append([1, 1])
    print(len(ans))
    for a, b in ans: print(a, b)








if __name__ == '__main__':
    main()
0