結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー ygd.
提出日時 2021-03-04 00:25:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,199 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 81,704 KB
最終ジャッジ日時 2024-10-03 18:52:47
合計ジャッジ時間 22,533 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import itertools
N,W = map(int,input().split()); INF = 1<<60
X=[];Y=[];R=[];V=[];A=[];SET =set([])
for _ in range(N):
    x,y,r,v,a = map(int,input().split())
    if (x,y,r,v,a) in SET:
        continue
    X.append(x);Y.append(y);R.append(r);V.append(v);A.append(a)
    SET.add((x,y,r,v,a))
#print(X,Y)
def touch(p,q,t,i): #今(p,q)に時間tでいてi番目の寿司を手に入れるのにかかる時間と最後の座標
    x = X[i]; y = Y[i]; r = R[i]; v = V[i]; a = A[i]
    sx = x + r*math.cos(math.radians(v*t+a))
    sy = y + r*math.sin(math.radians(v*t+a))
    if (p,q) == (sx,sy):
        return p,q,t
    ng = 0
    ok = 1000
    E = pow(10,-10)
    while abs(ok-ng) > E:
        mid = (ok+ng)/2
        mx = x + r*math.cos(math.radians(v*(t+mid)+a))
        my = y + r*math.sin(math.radians(v*(t+mid)+a))
        dis2 = pow(mx-p,2) + pow(my-q,2)
        if dis2 <= (mid*W)**2:
            ok = mid
        else:
            ng = mid
    nt = t + ok
    np = x + r*math.cos(math.radians(v*nt+a))
    nq =  y + r*math.sin(math.radians(v*nt+a))
    return np, nq, nt

N = len(SET)+1
#dp[S][v]:= 頂点0からスタートして、{0,1,2,…,n-1} の部分集合 S を巡回する |S|! 通りの経路のうち最後にvとなる最短時間。
dp = [[INF]*N for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1<<N):
    for v in range(N):
        for u in range(N): 
            if S != 0 and S&(1<<u) == 0: #空でないのにuが入っていないとダメ。
                continue
            if S&1<<v == 0: #Sにvがすでに入っていたら見る必要がない。
                if v != u: #集合Sにvを加えたときの最小値
                    t = dp[S][u]
                    if u == 0:
                        x0 = 0
                        y0 = 0
                    else:
                        x0 = X[u-1] + R[u-1]*math.cos(math.radians(V[u-1]*t+A[u-1]))
                        y0 = Y[u-1] + R[u-1]*math.sin(math.radians(V[u-1]*t+A[u-1]))
                    nx,ny,nt = touch(x0,y0,t,v-1)
                    #print("u",u,"v",v,t,nt,nx,ny)
                    dp[S|(1<<v)][v] = min(dp[S|(1<<v)][v], nt)
#print(dp)
ans = dp[(1<<N) - 1][0]
print(ans)
0