結果

問題 No.5007 Steiner Space Travel
ユーザー AkariAkari
提出日時 2022-07-30 17:57:27
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 422 ms / 1,000 ms
コード長 2,606 bytes
コンパイル時間 257 ms
実行使用メモリ 47,672 KB
スコア 8,002,865
最終ジャッジ日時 2022-07-30 17:57:49
合計ジャッジ時間 12,344 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 272 ms
47,168 KB
testcase_01 AC 422 ms
47,672 KB
testcase_02 AC 285 ms
47,068 KB
testcase_03 AC 225 ms
46,732 KB
testcase_04 AC 281 ms
47,436 KB
testcase_05 AC 313 ms
47,088 KB
testcase_06 AC 311 ms
47,096 KB
testcase_07 AC 356 ms
47,256 KB
testcase_08 AC 232 ms
47,108 KB
testcase_09 AC 248 ms
46,872 KB
testcase_10 AC 275 ms
46,912 KB
testcase_11 AC 312 ms
46,956 KB
testcase_12 AC 314 ms
47,128 KB
testcase_13 AC 252 ms
46,892 KB
testcase_14 AC 294 ms
46,968 KB
testcase_15 AC 272 ms
47,128 KB
testcase_16 AC 262 ms
47,552 KB
testcase_17 AC 301 ms
46,912 KB
testcase_18 AC 348 ms
47,388 KB
testcase_19 AC 296 ms
47,028 KB
testcase_20 AC 309 ms
47,224 KB
testcase_21 AC 241 ms
47,268 KB
testcase_22 AC 244 ms
47,080 KB
testcase_23 AC 312 ms
47,320 KB
testcase_24 AC 309 ms
47,124 KB
testcase_25 AC 313 ms
47,268 KB
testcase_26 AC 307 ms
46,712 KB
testcase_27 AC 235 ms
46,680 KB
testcase_28 AC 226 ms
47,196 KB
testcase_29 AC 293 ms
47,352 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 < 12 else greedy(cost)
        if V[U[0]] == 0:
            s = 2
            u = U[1]
        else:
            s = 1
            u = U[0]
        ans.append([1, V[u] + 1])
        for nu in U[s:]:
            if V[nu] == 0: continue
            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