結果

問題 No.1413 Dynamic Sushi
ユーザー lam6er
提出日時 2025-04-16 16:37:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,038 ms / 4,000 ms
コード長 3,516 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 81,796 KB
実行使用メモリ 77,720 KB
最終ジャッジ日時 2025-04-16 16:39:53
合計ジャッジ時間 20,321 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, W = int(input[idx]), int(input[idx+1])
    idx += 2
    sushis = []
    for _ in range(N):
        X = int(input[idx])
        Y = int(input[idx+1])
        R = int(input[idx+2])
        V = int(input[idx+3])
        A = int(input[idx+4])
        sushis.append((X, Y, R, V, A))
        idx += 5
    
    INF = float('inf')
    dp = [[INF] * (N + 1) for _ in range(1 << N)]
    dp[0][N] = 0.0  # Starting at virtual node (0,0) at time 0
    
    for mask in range(1 << N):
        for last in range(N + 1):
            if dp[mask][last] == INF:
                continue
            if mask == (1 << N) - 1:
                continue
            for i in range(N):
                if (mask >> i) & 1:
                    continue
                # Compute previous position and time
                if last == N:
                    x_prev, y_prev = 0.0, 0.0
                    t_prev = dp[mask][last]
                else:
                    X_prev, Y_prev, R_prev, V_prev, A_prev = sushis[last]
                    t_prev_current = dp[mask][last]
                    angle_prev = (V_prev * t_prev_current + A_prev) * math.pi / 180.0
                    x_prev = X_prev + R_prev * math.cos(angle_prev)
                    y_prev = Y_prev + R_prev * math.sin(angle_prev)
                    t_prev = t_prev_current
                # Compute for sushi i
                X_i, Y_i, R_i, V_i, A_i = sushis[i]
                # Initial check at t_prev
                angle_i_prev = (V_i * t_prev + A_i) * math.pi / 180.0
                x_i_prev = X_i + R_i * math.cos(angle_i_prev)
                y_i_prev = Y_i + R_i * math.sin(angle_i_prev)
                dx = x_i_prev - x_prev
                dy = y_i_prev - y_prev
                d_initial_sq = dx * dx + dy * dy
                if d_initial_sq < 1e-9:
                    t_new = t_prev
                else:
                    S_i = R_i * abs(V_i) * math.pi / 180.0
                    d_initial = math.sqrt(d_initial_sq)
                    upper_bound = t_prev + d_initial / (W - S_i) + 1.0
                    low = t_prev
                    high = upper_bound
                    best_t = None
                    eps = 1e-8
                    for _ in range(100):
                        mid = (low + high) / 2
                        angle_i = (V_i * mid + A_i) * math.pi / 180.0
                        x_i = X_i + R_i * math.cos(angle_i)
                        y_i = Y_i + R_i * math.sin(angle_i)
                        dx_curr = x_i - x_prev
                        dy_curr = y_i - y_prev
                        distance_sq = dx_curr ** 2 + dy_curr ** 2
                        allowed = W * (mid - t_prev)
                        allowed_sq = allowed ** 2
                        if distance_sq <= allowed_sq + 1e-9:
                            best_t = mid
                            high = mid - eps
                        else:
                            low = mid + eps
                    if best_t is None:
                        continue
                    t_new = best_t
                new_mask = mask | (1 << i)
                if t_new < dp[new_mask][i]:
                    dp[new_mask][i] = t_new
    
    full_mask = (1 << N) - 1
    min_time = INF
    for i in range(N):
        if dp[full_mask][i] < min_time:
            min_time = dp[full_mask][i]
    print("{0:.11f}".format(min_time))

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