結果

問題 No.5007 Steiner Space Travel
ユーザー dna4_dna4_
提出日時 2023-04-24 12:44:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 945 ms / 1,000 ms
コード長 5,866 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 87,408 KB
実行使用メモリ 81,592 KB
スコア 7,416,643
最終ジャッジ日時 2023-04-24 12:45:14
合計ジャッジ時間 31,504 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 927 ms
80,660 KB
testcase_01 AC 928 ms
80,572 KB
testcase_02 AC 927 ms
79,704 KB
testcase_03 AC 927 ms
79,972 KB
testcase_04 AC 925 ms
80,312 KB
testcase_05 AC 945 ms
79,960 KB
testcase_06 AC 928 ms
80,124 KB
testcase_07 AC 931 ms
80,032 KB
testcase_08 AC 931 ms
80,920 KB
testcase_09 AC 933 ms
79,856 KB
testcase_10 AC 928 ms
80,548 KB
testcase_11 AC 930 ms
80,252 KB
testcase_12 AC 934 ms
80,244 KB
testcase_13 AC 928 ms
79,988 KB
testcase_14 AC 927 ms
80,220 KB
testcase_15 AC 928 ms
80,660 KB
testcase_16 AC 928 ms
80,364 KB
testcase_17 AC 941 ms
79,860 KB
testcase_18 AC 929 ms
80,460 KB
testcase_19 AC 928 ms
81,592 KB
testcase_20 AC 929 ms
79,780 KB
testcase_21 AC 941 ms
80,540 KB
testcase_22 AC 930 ms
79,980 KB
testcase_23 AC 928 ms
79,952 KB
testcase_24 AC 928 ms
79,888 KB
testcase_25 AC 931 ms
80,020 KB
testcase_26 AC 928 ms
80,308 KB
testcase_27 AC 927 ms
80,648 KB
testcase_28 AC 929 ms
80,276 KB
testcase_29 AC 930 ms
80,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
import random
import math

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 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

    def __str__(self) -> str:
        return f"({self.id},{self.x},{self.y},{self.type})"

class State:
    
    def __init__(self, order:list, q_planets:list, q_stations:list) -> None:
        """
        order:list visited order 
        q_stations:list[(int,int)] coordinates of space station
        """
        self.order = order
        self.q_planets = q_planets
        self.q_stations = q_stations
    
    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 = 1 # station to station
        if v1.type == 1 and v2.type == 1: coef = alpha2 # planet to planet
        elif v1.type == 2 or v2.type == 2: coef = alpha # planet to station or station to planet
        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))
    
class Output:
    
    def __init__(self, state:State) -> None:
        self.order = state.order
        self.q_stations = state.q_stations

    def ans(self):
        for transition in self.q_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.q_planets[0])
        visited = [0]*len(self.state.q_planets)
        visited[0] = 1
        now = self.state.q_planets[0]
        next = Transit(-1,-1,-1,-1)
        while sum(visited) < len(self.state.q_planets):
            d_min = INF
            for transtion in self.state.q_planets:
                if visited[transtion.id] == 1: continue
                d = self.state.cal_dist(now, transtion)
                if d_min > d:
                    d_min = d
                    next = transtion
            if now.type != 2: #station to stationを許可するときはこのif文を消す　要改善
                for transtion in self.state.q_stations:
                    if now == transtion: continue
                    d = self.state.cal_dist(now, transtion)
                    if d_min > d:
                        d_min = d
                        next = transtion
            now = next
            self.state.order.append(next)
            if next.type == 1:
                visited[next.id] = 1

        self.state.order.append(self.state.q_planets[0])
        return self.state

def main():

    parser = Parser(-1)
    input = parser.parse()
    
    q_planets = []
    for i in range(input.N):
        q_planets.append(Transit(id = i, x = input.ab[i][0], y = input.ab[i][1], type = 1))
    
    best_score = -1
    best_ans = None
    timeKeeper = TimeKeeper(0.83)
    while not timeKeeper.isTimeOver():
        order = []
        q_stations = []
        for i in range(input.M):
            q_stations.append(Transit(id = i,x = random.randrange(100,900),y = random.randrange(100,900),type = 2))
        state = State(order,q_planets,q_stations)
        solver = Solver(state)
        ans = solver.solve()
        score = ans.cal_score()
        eprint(score)
        if score > best_score:
            best_score = score
            best_ans = ans
    eprint(best_score)
    output = Output(best_ans)
    output.ans()


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