結果

問題 No.1413 Dynamic Sushi
ユーザー lam6er
提出日時 2025-04-16 00:43:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,599 bytes
コンパイル時間 455 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 96,964 KB
最終ジャッジ日時 2025-04-16 00:47:15
合計ジャッジ時間 6,238 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import heapq

def main():
    N, W = map(int, input().split())
    sushi = []
    for _ in range(N):
        X, Y, R, V, A = map(int, input().split())
        sushi.append((X, Y, R, V, A))
    
    # Initialize the priority queue with the starting state (time 0, mask 0, last -1, position (0,0))
    heap = []
    heapq.heappush(heap, (0.0, 0, -1, 0.0, 0.0))
    
    best = {}
    best[(0, -1)] = (0.0, 0.0, 0.0)
    
    answer = float('inf')
    
    while heap:
        current_time, mask, last, x_prev, y_prev = heapq.heappop(heap)
        
        # If this state has been processed with a better time, skip
        if (mask, last) in best and best[(mask, last)][0] < current_time:
            continue
        
        # Check if all sushi are collected
        if mask == (1 << N) - 1:
            answer = min(answer, current_time)
            continue
        
        # Process transitions to each next sushi
        for i in range(N):
            if not (mask & (1 << i)):
                X_i, Y_i, R_i, V_i, A_i = sushi[i]
                
                # Function to compute f(dt) = distance - W * dt
                def compute_f(dt):
                    t = current_time + dt
                    theta = (V_i * t + A_i) * math.pi / 180.0
                    x = X_i + R_i * math.cos(theta)
                    y = Y_i + R_i * math.sin(theta)
                    dx = x - x_prev
                    dy = y - y_prev
                    distance = math.hypot(dx, dy)
                    return distance - W * dt
                
                # Find the minimal dt >= 0 where compute_f(dt) == 0
                dt = 0.0
                f0 = compute_f(dt)
                found = False
                
                if abs(f0) < 1e-9:
                    found = True
                elif f0 > 0:
                    # Need to find upper bound where compute_f becomes negative
                    dt_high = 1e-8
                    while compute_f(dt_high) > 0:
                        dt_high *= 2
                        if dt_high > 1e20:
                            break  # Safeguard against infinite loop
                    # Now perform binary search between dt_low=0 and dt_high
                    dt_low = 0.0
                    for _ in range(100):
                        dt_mid = (dt_low + dt_high) / 2
                        f_mid = compute_f(dt_mid)
                        if f_mid > 0:
                            dt_low = dt_mid
                        else:
                            dt_high = dt_mid
                    dt = dt_high
                    # Verify if the found dt is valid
                    if compute_f(dt) <= 1e-6:
                        found = True
                else:
                    # f0 < 0, which is impossible since distance can't be negative
                    continue
                
                if not found:
                    continue  # No valid dt found, skip this transition
                
                t = current_time + dt
                theta = (V_i * t + A_i) * math.pi / 180.0
                x = X_i + R_i * math.cos(theta)
                y = Y_i + R_i * math.sin(theta)
                new_mask = mask | (1 << i)
                new_key = (new_mask, i)
                
                # Update best time if this is better
                if t < best.get(new_key, (float('inf'), 0, 0))[0]:
                    best[new_key] = (t, x, y)
                    heapq.heappush(heap, (t, new_mask, i, x, y))
    
    print("{0:.15f}".format(answer))

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