結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:26:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,147 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 142,584 KB
最終ジャッジ日時 2025-03-20 20:28:31
合計ジャッジ時間 5,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    W = float(input[idx]); idx +=1
    
    X = []
    Y = []
    R = []
    V = []
    A = []
    for _ in range(N):
        x = float(input[idx]); idx +=1
        y = float(input[idx]); idx +=1
        r = float(input[idx]); idx +=1
        v = float(input[idx]); idx +=1
        a = float(input[idx]); idx +=1
        X.append(x)
        Y.append(y)
        R.append(r)
        V.append(v)
        A.append(a)
    
    INF = float('inf')
    dp = [[INF]*N for _ in range(1<<N)]
    
    # Initialize first step
    for v in range(N):
        # From (0,0) at time 0 to sushi v
        x_prev = 0.0
        y_prev = 0.0
        t_prev = 0.0
        
        Xv = X[v]
        Yv = Y[v]
        Rv = R[v]
        Vv = V[v]
        Av = A[v]
        
        # Function to calculate the required earliest time
        def xvt(t):
            return Xv + Rv * math.cos( (Vv * t + Av) * math.pi / 180 )
        def yvt(t):
            return Yv + Rv * math.sin( (Vv * t + Av) * math.pi / 180 )
        
        left = t_prev
        right = t_prev
        if math.hypot(x_prev - xvt(left), y_prev - yvt(left)) <= W * (left - t_prev):
            dp[1<<v][v] = left
            continue
        
        # Find right such that distance <= W*(right - t_prev)
        found = False
        step = 1e-8
        right = left + step
        for _ in range(100):
            xr = xvt(right)
            yr = yvt(right)
            d = math.hypot(x_prev - xr, y_prev - yr)
            if d <= W*(right - t_prev):
                found = True
                break
            step *= 2
            right += step
        
        if not found:
            # This should not happen as per problem statement
            continue
        
        # Binary search between left and right
        for _ in range(100):
            mid = (left + right)/2
            xmid = xvt(mid)
            ymid = yvt(mid)
            d_mid = math.hypot(x_prev -xmid, y_prev -ymid)
            if d_mid <= W*(mid - t_prev):
                right = mid
            else:
                left = mid
        
        dp[1<<v][v] = right
    
    # Iterate all masks
    for mask in range(1<<N):
        for u in range(N):
            if not (mask & (1<<u)):
                continue
            current_time = dp[mask][u]
            if current_time == INF:
                continue
            
            # Current position is sushi u's position at current_time
            xu = X[u] + R[u] * math.cos( (V[u] * current_time + A[u]) * math.pi / 180 )
            yu = Y[u] + R[u] * math.sin( (V[u] * current_time + A[u]) * math.pi / 180 )
            
            for v in range(N):
                if mask & (1<<v):
                    continue
                # Calculate earliest t_next >= current_time for sushi v
                Xv_val = X[v]
                Yv_val = Y[v]
                Rv_val = R[v]
                Vv_val = V[v]
                Av_val = A[v]
                
                def xvt(t):
                    return Xv_val + Rv_val * math.cos( (Vv_val * t + Av_val) * math.pi / 180 )
                def yvt(t):
                    return Yv_val + Rv_val * math.sin( (Vv_val * t + Av_val) * math.pi / 180 )
                
                left = current_time
                right = current_time
                
                # Check if left is already feasible
                d_left = math.hypot(xu - xvt(left), yu - yvt(left))
                if d_left <= W * (left - current_time):
                    t_candidate = left
                else:
                    # Find upper bound
                    step = 1e-8
                    right = left + step
                    found = False
                    for _ in range(100):
                        xr = xvt(right)
                        yr = yvt(right)
                        d = math.hypot(xu -xr, yu -yr)
                        if d <= W*(right - current_time):
                            found = True
                            break
                        step *= 2
                        right += step
                    if not found:
                        continue  # should not happen
                    # Binary search
                    for _ in range(100):
                        mid = (left + right)/2
                        xmid = xvt(mid)
                        ymid = yvt(mid)
                        d_mid = math.hypot(xu -xmid, yu -ymid)
                        if d_mid <= W*(mid - current_time):
                            right = mid
                        else:
                            left = mid
                    t_candidate = right
                
                new_mask = mask | (1<<v)
                if t_candidate < dp[new_mask][v]:
                    dp[new_mask][v] = t_candidate
    
    full_mask = (1<<N) -1
    min_time = INF
    for u in range(N):
        if dp[full_mask][u] < min_time:
            min_time = dp[full_mask][u]
    
    print("{0:.15f}".format(min_time))

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