結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:40:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,274 ms / 4,000 ms
コード長 3,279 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 81,628 KB
実行使用メモリ 90,196 KB
最終ジャッジ日時 2025-04-16 00:43:30
合計ジャッジ時間 23,891 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import heapq

def main():
    N, W = map(int, input().split())
    sushis = []
    for _ in range(N):
        X, Y, R, V, A = map(int, input().split())
        sushis.append((X, Y, R, V, A))
    
    heap = []
    heapq.heappush(heap, (0.0, 0, -1))
    dp = {}
    dp[(0, -1)] = 0.0
    
    best_time = None
    
    while heap:
        current_time, mask, u = heapq.heappop(heap)
        
        if (mask, u) in dp and dp[(mask, u)] < current_time:
            continue
        
        if mask == (1 << N) - 1:
            best_time = current_time
            print("{0:.15f}".format(best_time))
            return
        
        for v in range(N):
            if not (mask & (1 << v)):
                if u == -1:
                    u_pos = (0.0, 0.0)
                    t_start = 0.0
                else:
                    X_u, Y_u, R_u, V_u, A_u = sushis[u]
                    angle_u = (V_u * current_time + A_u) * math.pi / 180.0
                    x_u = X_u + R_u * math.cos(angle_u)
                    y_u = Y_u + R_u * math.sin(angle_u)
                    u_pos = (x_u, y_u)
                    t_start = current_time
                
                X_v, Y_v, R_v, V_v, A_v = sushis[v]
                def get_v_pos(delta):
                    angle = (V_v * (t_start + delta) + A_v) * math.pi / 180.0
                    x = X_v + R_v * math.cos(angle)
                    y = Y_v + R_v * math.sin(angle)
                    return (x, y)
                
                xv0, yv0 = get_v_pos(0.0)
                dx0 = xv0 - u_pos[0]
                dy0 = yv0 - u_pos[1]
                dist_sq0 = dx0**2 + dy0**2
                if dist_sq0 <= (W * 0.0)**2 + 1e-12:
                    delta = 0.0
                else:
                    low = 0.0
                    high = 1.0
                    found = False
                    for _ in range(30):
                        xvh, yvh = get_v_pos(high)
                        dxh = xvh - u_pos[0]
                        dyh = yvh - u_pos[1]
                        dist_sqh = dxh**2 + dyh**2
                        if dist_sqh <= (W * high)**2 + 1e-12:
                            found = True
                            break
                        high *= 2
                    if not found:
                        high = 1e20
                    eps = 1e-12
                    for _ in range(100):
                        mid = (low + high) / 2
                        xvm, yvm = get_v_pos(mid)
                        dxm = xvm - u_pos[0]
                        dym = yvm - u_pos[1]
                        dist_sqm = dxm**2 + dym**2
                        w_sq = (W * mid)**2
                        if dist_sqm <= w_sq + eps:
                            high = mid
                        else:
                            low = mid
                    delta = high
                
                new_time = current_time + delta
                new_mask = mask | (1 << v)
                key = (new_mask, v)
                if key not in dp or new_time < dp.get(key, float('inf')):
                    dp[key] = new_time
                    heapq.heappush(heap, (new_time, new_mask, v))
    
    print("{0:.15f}".format(best_time))

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