結果

問題 No.5007 Steiner Space Travel
ユーザー AkariAkari
提出日時 2022-07-30 15:56:50
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 286 ms / 1,000 ms
コード長 2,300 bytes
コンパイル時間 302 ms
実行使用メモリ 78,968 KB
スコア 7,344,627
最終ジャッジ日時 2022-07-30 15:57:03
合計ジャッジ時間 11,498 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 286 ms
47,404 KB
testcase_01 AC 256 ms
47,072 KB
testcase_02 AC 256 ms
46,880 KB
testcase_03 AC 243 ms
46,928 KB
testcase_04 AC 224 ms
46,972 KB
testcase_05 AC 232 ms
47,112 KB
testcase_06 AC 239 ms
46,976 KB
testcase_07 AC 248 ms
46,672 KB
testcase_08 AC 246 ms
46,844 KB
testcase_09 AC 256 ms
47,164 KB
testcase_10 AC 234 ms
46,888 KB
testcase_11 AC 244 ms
46,708 KB
testcase_12 AC 231 ms
47,376 KB
testcase_13 AC 247 ms
46,908 KB
testcase_14 AC 250 ms
46,940 KB
testcase_15 AC 236 ms
46,932 KB
testcase_16 AC 242 ms
46,852 KB
testcase_17 AC 238 ms
47,284 KB
testcase_18 AC 241 ms
46,700 KB
testcase_19 AC 242 ms
46,908 KB
testcase_20 AC 236 ms
47,108 KB
testcase_21 AC 238 ms
46,884 KB
testcase_22 AC 250 ms
47,124 KB
testcase_23 AC 247 ms
46,532 KB
testcase_24 AC 240 ms
46,904 KB
testcase_25 AC 237 ms
46,664 KB
testcase_26 AC 242 ms
46,960 KB
testcase_27 AC 246 ms
47,012 KB
testcase_28 AC 245 ms
47,212 KB
testcase_29 AC 243 ms
78,968 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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():
    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, 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]))
    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 < 10 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([1, 1])
    print(len(ans))
    for a, b in ans: print(a, b)








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