結果

問題 No.5007 Steiner Space Travel
ユーザー dna4_dna4_
提出日時 2023-04-25 15:00:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 979 ms / 1,000 ms
コード長 10,715 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 87,020 KB
実行使用メモリ 103,064 KB
スコア 8,291,752
最終ジャッジ日時 2023-04-25 15:01:18
合計ジャッジ時間 32,760 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 970 ms
101,844 KB
testcase_01 AC 958 ms
97,888 KB
testcase_02 AC 959 ms
99,480 KB
testcase_03 AC 958 ms
98,172 KB
testcase_04 AC 964 ms
98,424 KB
testcase_05 AC 951 ms
98,632 KB
testcase_06 AC 964 ms
98,868 KB
testcase_07 AC 960 ms
98,992 KB
testcase_08 AC 956 ms
99,568 KB
testcase_09 AC 954 ms
98,748 KB
testcase_10 AC 976 ms
99,540 KB
testcase_11 AC 962 ms
98,972 KB
testcase_12 AC 978 ms
99,032 KB
testcase_13 AC 967 ms
97,408 KB
testcase_14 AC 960 ms
98,980 KB
testcase_15 AC 964 ms
101,056 KB
testcase_16 AC 958 ms
99,212 KB
testcase_17 AC 956 ms
99,580 KB
testcase_18 AC 963 ms
98,960 KB
testcase_19 AC 955 ms
98,876 KB
testcase_20 AC 966 ms
103,064 KB
testcase_21 AC 973 ms
100,524 KB
testcase_22 AC 951 ms
100,132 KB
testcase_23 AC 979 ms
99,012 KB
testcase_24 AC 974 ms
102,748 KB
testcase_25 AC 951 ms
98,604 KB
testcase_26 AC 970 ms
98,316 KB
testcase_27 AC 972 ms
101,160 KB
testcase_28 AC 955 ms
100,880 KB
testcase_29 AC 965 ms
100,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import time
import random
import math
import heapq
from collections import defaultdict

random.seed(42)

INF = 10**18

alpha = 5
alpha2 = alpha * alpha

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

class TimeKeeper:
    """
    時間を管理するクラス
    時間制限を秒単位で指定してインスタンスをつくる
    """
 
    def __init__(self, time_threshold) -> None:
        self.start_time_ = time.time()
        self.time_threshold_ = time_threshold
 
    def isTimeOver(self) -> bool:
        """
        インスタンスを生成した時から指定した時間制限を超過したか判断する  
        超過している場合にTrue  
        """
        return time.time() - self.start_time_ - self.time_threshold_ >= 0
 
    def time_msec(self) -> int:
        """経過時間をミリ秒単位で返す"""
        return int((time.time() - self.start_time_) * 1000)

    def time_sec(self) -> int:
        """経過時間を秒単位で返す(time_msecの使用を推奨)"""
        return time.time()-self.start_time_

class Kmeans:
    
    def __init__(self, X:list, n_data:int, k:int):
        self.x = [[t.x, t.y] for t in X]
        self.n_data = n_data
        self.k = k

    def init_centroid(self):
        idx = random.sample(range(self.n_data), self.k)
        centroids = [self.x[i] for i in idx]
        return centroids
    
    def compute_distance(self, centroids):
        distances = []
        for x in self.x:
            dist = [math.sqrt(sum([(a - b) ** 2 for a, b in zip(x, centroid)])) for centroid in centroids]
            distances.append(dist)
        return distances
    
    def clustering(self):
        centroids = self.init_centroid()
        new_cluster = [0]*self.n_data
        cluster = [0]*self.n_data
        for epoch in range(100):
            distances = self.compute_distance(centroids)
            new_cluster = [min(range(len(d)), key=lambda i: d[i]) for d in distances]
            for idx_centroid in range(self.k):
                x_in_cluster = [self.x[i] for i in range(self.n_data) if new_cluster[i] == idx_centroid]
                if x_in_cluster:
                    centroids[idx_centroid] = [int(sum(coord)/len(x_in_cluster)) for coord in zip(*x_in_cluster)]
            if new_cluster == cluster:
                break
        #cluster = new_cluster
        return centroids


class Input:
    def __init__(self, N:int, M:int, ab:list) -> None:
        self.N = N
        self.M = M
        self.ab = ab

class Parser:

    def __init__(self, input_type:int):
        self.flag = input_type

    def parse(self):
        if self.flag == -1:
            inp:Input = self.parse_input()
        else:
            inp:Input = self.parse_input_file(self.flag)
        return inp
    
    def parse_input(self) -> Input:
        N,M = map(int,input().split())
        ab = [list(map(int,input().split())) for i in range(N)]
        return Input(N,M,ab)


    def parse_input_file(self,num) -> Input:
        cnt = str(num).zfill(4)
        PATH = f"./in/{cnt}.txt"
        with open(PATH) as f:
            l = [s.strip() for s in f.readlines()]
            N, M = map(int,l[0].split())
            ab = [list(map(int,s.split())) for s in l[1:]]
            return Input(N, M, ab)

class Transit:

    def __init__(self, id:int, x:int, y:int, type:int) -> None:
        """
        id:int id of planet or station
        x:int x coordinate
        y:int y coordinate
        type:int 1 planet, 2 station
        """
        self.id = id
        self.x = x
        self.y = y
        self.type = type
        self.key = self.type * 1000 + self.id

    def __lt__(self, other) -> bool:
        return self.key < other.key
    
    def __eq__(self, other) -> bool:
        return self.key == other.key
    
    def __str__(self) -> str:
        return f"({self.id},{self.x},{self.y},{self.type})"

class State:
    
    def __init__(self, order:list, planets:list, stations:list, dist_mat:list) -> None:
        """
        order:list visited order 
        stations:list[(int,int)] coordinates of space station
        """
        self.order = order
        self.planets = planets
        self.stations = stations
        self.links = self.prepare_edges()
        self.dist_mat = dist_mat
    
    def prepare_edges(self):
        """
        edges:dictを返す
        edges[Transit_from_key:int] = [(dist, Transit_to), ...]
        """
        edges = defaultdict(list)
        for planet_from in self.planets:
            for planet_to in self.planets: # planet to planet
                if planet_from == planet_to: continue
                edges[planet_from.key].append((self.cal_dist(planet_from, planet_to), planet_to))
            for station_to in self.stations: # planet to station
                edges[planet_from.key].append((self.cal_dist(planet_from, station_to), station_to))
        for station_from in self.stations: # station to station
            for planet_to in self.planets:
                edges[station_from.key].append((self.cal_dist(station_from, planet_to), planet_to))
            for station_to in self.stations:
                if station_from == station_to: continue
                edges[station_from.key].append((self.cal_dist(station_from, station_to), station_to))
        return edges

    
    def cal_dist(self, v1:Transit, v2:Transit) -> float:
        """
        return distance between v1 and v2 weighted by coefficient
        """
        x1,y1 = v1.x, v1.y
        x2,y2 = v2.x, v2.y
        coef = alpha
        if v1.type == 1 and v2.type == 1: coef = alpha2 # planet to planet
        elif v1.type == 2 and v2.type == 2: coef = 1 # station to station
        d = ((x1-x2)**2+(y1-y2)**2) * coef
        return d
    
    def cal_score(self):
        score = 0
        for i in range(len(self.order)-1):
            score += self.cal_dist(self.order[i], self.order[i+1])
        return int(pow(10,9)/(1000+score**0.5))

def trace(start:Transit, target:Transit, ancestors): 
    # s:source, t:target
    # dijksttra法の経路復元
    route = [target]
    now = target
    while True:
        pre = ancestors[now.key]
        route.append(pre)
        if pre == start:
            break
        now = pre
    route.reverse()
    return route

def dijkstra(start:Transit, target:Transit, links):
    heap = [(*l,start) for l in links[start.key]]
    heapq.heapify(heap)
    visited = set([start.key])
    ancestors = defaultdict(int)
    while heap:
        cost, to, ancestor = heapq.heappop(heap)
        if to.key in visited:
            continue
        visited.add(to.key)
        ancestors[to.key] = ancestor
        if to == target:
            return cost, trace(start,target,ancestors)
        for cost2, node2 in links[to.key]:
            if node2.key not in visited:
                heapq.heappush(heap, (cost+cost2, node2, to))
    return INF, None

def warshall_floyd(planets:list):
    n = len(planets)
    dist = [[INF]*n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i in range(n):
        for j in range(i+1,n):
            d = (planets[i].x - planets[j].x) ** 2 + (planets[i].y - planets[j].y) ** 2
            dist[i][j] = d
            dist[j][i] = d
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


class Output:
    
    def __init__(self, state:State) -> None:
        self.order = state.order
        self.stations = state.stations

    def ans(self):
        for transition in self.stations:
            print(transition.x, transition.y)
        print(len(self.order))
        for transition in self.order:
            print(transition.type, transition.id+1)

class Solver:
    def __init__(self, state:State) -> None:
        self.state = state
    
    def solve(self):
        
        self.state.order.append(self.state.planets[0])
        visited = [0]*len(self.state.planets)
        visited[0] = 1
        now = self.state.planets[0]
        next = Transit(-1,-1,-1,-1)
        n_visited = set([0])
        
        while len(n_visited) < len(self.state.planets):
            next_dist = []
            for i in range(len(self.state.planets)):
                next_dist.append((self.state.dist_mat[now.id][i], i))
            next_dist = sorted(next_dist, key=lambda x:x[0])
            for i in range(len(self.state.planets)):
                if visited[next_dist[i][1]] == 1: continue
                next = self.state.planets[next_dist[i][1]]
                break
            _, route = dijkstra(now, next, self.state.links)
            for transition in route:
                self.state.order.append(transition)
            now = next
            visited[next.id] = 1
            n_visited.add(next.id)

        _, route = dijkstra(now, self.state.planets[0], self.state.links)
        for transition in route:
            self.state.order.append(transition)
    
        return self.state

def main():

    timeKeeper2 = TimeKeeper(0.83)

    parser = Parser(-1)
    input = parser.parse()
    
    planets = []
    for i in range(input.N):
        planets.append(Transit(id = i, x = input.ab[i][0], y = input.ab[i][1], type = 1))
    dist_mat = warshall_floyd(planets)

    kmeans_center = Kmeans(planets, 100, 8).clustering()
    stations = []
    for i in range(input.M):
        stations.append(Transit(id = i,x = kmeans_center[i][0],y = kmeans_center[i][1],type = 2))
    
    state = State([], planets, stations, dist_mat)
    solver = Solver(state)
    best_ans = solver.solve()
    best_score = best_ans.cal_score()
    #eprint(timeKeeper2.time_msec(), best_score)

    tmp_stations = best_ans.stations
    
    while not timeKeeper2.isTimeOver():
        order = []
        stations = []
        for i in range(input.M):
            x_new = 0
            y_new = 0
            while True:
                x_new = tmp_stations[i].x+random.randrange(-20,20)
                y_new = tmp_stations[i].y+random.randrange(-20,20)
                if x_new >= 0 and x_new <= 1000 and y_new >= 0 and y_new <= 1000:
                    break
            stations.append(Transit(id = i,x = x_new, y = y_new, type = 2))
        state = State(order,planets,stations, dist_mat)
        solver = Solver(state)
        ans = solver.solve()
        score = ans.cal_score()
        #eprint(timeKeeper2.time_msec(), score)
        if score > best_score:
            best_score = score
            best_ans = ans
            tmp_stations = stations
    eprint(best_score)
    output = Output(best_ans)
    output.ans()


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