結果

問題 No.5007 Steiner Space Travel
ユーザー AkariAkari
提出日時 2022-07-30 16:46:29
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 307 ms
47,268 KB
testcase_01 AC 312 ms
47,252 KB
testcase_02 AC 329 ms
47,292 KB
testcase_03 AC 252 ms
46,864 KB
testcase_04 AC 303 ms
47,152 KB
testcase_05 AC 333 ms
47,272 KB
testcase_06 AC 258 ms
46,908 KB
testcase_07 AC 296 ms
47,284 KB
testcase_08 AC 236 ms
47,040 KB
testcase_09 AC 272 ms
46,924 KB
testcase_10 AC 235 ms
46,976 KB
testcase_11 AC 250 ms
46,880 KB
testcase_12 AC 268 ms
47,420 KB
testcase_13 AC 290 ms
47,088 KB
testcase_14 AC 249 ms
46,984 KB
testcase_15 AC 302 ms
47,072 KB
testcase_16 AC 266 ms
46,832 KB
testcase_17 AC 250 ms
46,972 KB
testcase_18 AC 273 ms
47,256 KB
testcase_19 AC 250 ms
47,112 KB
testcase_20 AC 270 ms
47,404 KB
testcase_21 AC 246 ms
47,172 KB
testcase_22 AC 270 ms
46,860 KB
testcase_23 AC 271 ms
47,340 KB
testcase_24 AC 286 ms
47,140 KB
testcase_25 AC 275 ms
47,152 KB
testcase_26 AC 241 ms
47,044 KB
testcase_27 AC 260 ms
46,704 KB
testcase_28 AC 258 ms
47,132 KB
testcase_29 AC 252 ms
86,396 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():
    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