結果

問題 No.5007 Steiner Space Travel
ユーザー AkariAkari
提出日時 2022-07-30 17:48:41
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,603 bytes
コンパイル時間 61 ms
実行使用メモリ 47,664 KB
スコア 3,444,863
最終ジャッジ日時 2022-07-30 17:49:02
合計ジャッジ時間 17,038 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge16
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 415 ms
47,284 KB
testcase_02 WA -
testcase_03 AC 248 ms
47,072 KB
testcase_04 WA -
testcase_05 AC 299 ms
47,272 KB
testcase_06 AC 300 ms
47,160 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 256 ms
46,748 KB
testcase_10 WA -
testcase_11 AC 301 ms
47,124 KB
testcase_12 AC 292 ms
47,152 KB
testcase_13 WA -
testcase_14 AC 316 ms
46,716 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 341 ms
47,412 KB
testcase_25 AC 300 ms
47,132 KB
testcase_26 AC 267 ms
47,228 KB
testcase_27 WA -
testcase_28 AC 235 ms
47,216 KB
testcase_29 AC 274 ms
47,344 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 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