結果

問題 No.1413 Dynamic Sushi
ユーザー lam6er
提出日時 2025-03-31 17:33:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,238 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 85,936 KB
最終ジャッジ日時 2025-03-31 17:34:36
合計ジャッジ時間 6,178 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    index = 0
    N = int(data[index])
    index += 1
    W = int(data[index])
    index += 1

    sushis = []
    for _ in range(N):
        X = int(data[index])
        index +=1
        Y = int(data[index])
        index +=1
        R = int(data[index])
        index +=1
        V = int(data[index])
        index +=1
        A = int(data[index])
        index +=1
        sushis.append( (X, Y, R, V, A) )

    INF = float('inf')
    size = 1 << N
    dp = [ [INF] * N for _ in range(size) ]

    # Initialize for single sushi states
    for j in range(N):
        Xj, Yj, Rj, Vj, Aj = sushis[j]
        start_pos = (0.0, 0.0)
        start_time = 0.0

        # Function to compute sushi j's position at time t
        def j_pos(t):
            theta = (Vj * t + Aj) * math.pi / 180.0
            x = Xj + Rj * math.cos(theta)
            y = Yj + Rj * math.sin(theta)
            return (x, y)
        
        # Binary search for the minimal t_j where distance from start_pos <= W * t_j
        low = 0.0
        high = 1e18  # Initial upper bound

        # Initial check at t=0
        initial_x, initial_y = j_pos(0.0)
        dx = initial_x - 0.0
        dy = initial_y - 0.0
        initial_dist = math.hypot(dx, dy)
        if initial_dist < 1e-9:
            dp[1<<j][j] = 0.0
            continue

        # Otherwise, proceed with binary search
        for _ in range(100):
            mid = (low + high) / 2
            x, y = j_pos(mid)
            dx = x - start_pos[0]
            dy = y - start_pos[1]
            dist = math.hypot(dx, dy)
            allowed = W * mid
            if dist <= allowed + 1e-9:
                high = mid
            else:
                low = mid

        # Check high
        x_high, y_high = j_pos(high)
        dx = x_high - start_pos[0]
        dy = y_high - start_pos[1]
        dist_high = math.hypot(dx, dy)
        if dist_high <= W * high + 1e-9:
            dp[1 << j][j] = high

    # Process all masks and transitions
    for mask in range(size):
        for i in range(N):
            if not (mask & (1 << i)):
                continue
            current_time = dp[mask][i]
            if current_time == INF:
                continue

            # Current position of sushi i at current_time
            Xi, Yi, Ri, Vi, Ai = sushis[i]
            theta_i = (Vi * current_time + Ai) * math.pi / 180.0
            xi = Xi + Ri * math.cos(theta_i)
            yi = Yi + Ri * math.sin(theta_i)
            start_pos = (xi, yi)

            for j in range(N):
                if mask & (1 << j):
                    continue

                Xj, Yj, Rj, Vj, Aj = sushis[j]

                # Function to compute j's position
                def j_pos(t):
                    theta = (Vj * t + Aj) * math.pi / 180.0
                    x = Xj + Rj * math.cos(theta)
                    y = Yj + Rj * math.sin(theta)
                    return (x, y)

                # Binary search for minimal t_j >= current_time
                # where distance from start_pos to j's position <= W*(t_j - current_time)
                low = current_time
                high = current_time + 1e18  # Initial upper bound

                # Check if starting position already covers it
                x_initial, y_initial = j_pos(current_time)
                dx_initial = x_initial - xi
                dy_initial = y_initial - yi
                initial_dist = math.hypot(dx_initial, dy_initial)
                if initial_dist < 1e-9:
                    new_mask = mask | (1 << j)
                    if current_time < dp[new_mask][j]:
                        dp[new_mask][j] = current_time
                    continue

                # Compute upper bound based on speed considerations
                S_j = Rj * abs(Vj) * math.pi / 180.0
                initial_upper = current_time + initial_dist / (W - S_j + 1e-9)
                high = initial_upper

                # Binary search
                for _ in range(100):
                    mid = (low + high) / 2
                    x, y = j_pos(mid)
                    dx = x - xi
                    dy = y - yi
                    dist = math.hypot(dx, dy)
                    allowed = W * (mid - current_time)
                    if dist <= allowed + 1e-9:
                        high = mid
                    else:
                        low = mid

                # After binary search, check high
                x_high, y_high = j_pos(high)
                dx = x_high - xi
                dy = y_high - yi
                dist_high = math.hypot(dx, dy)
                allowed = W * (high - current_time)
                if dist_high <= allowed + 1e-9:
                    new_time = high
                    new_mask = mask | (1 << j)
                    if new_time < dp[new_mask][j]:
                        dp[new_mask][j] = new_time

    # Find the minimal time for full mask
    full_mask = (1 << N) - 1
    min_time = INF
    for j in range(N):
        if dp[full_mask][j] < min_time:
            min_time = dp[full_mask][j]
    
    print("{0:.15f}".format(min_time))

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