結果

問題 No.1413 Dynamic Sushi
ユーザー ygd.ygd.
提出日時 2021-03-04 00:36:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,285 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 82,928 KB
最終ジャッジ日時 2024-04-14 19:07:41
合計ジャッジ時間 83,234 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 OLE -
testcase_05 OLE -
testcase_06 OLE -
testcase_07 OLE -
testcase_08 OLE -
testcase_09 OLE -
testcase_10 OLE -
testcase_11 OLE -
testcase_12 OLE -
testcase_13 OLE -
testcase_14 OLE -
testcase_15 OLE -
testcase_16 OLE -
testcase_17 OLE -
testcase_18 OLE -
testcase_19 OLE -
testcase_20 WA -
testcase_21 WA -
testcase_22 OLE -
testcase_23 OLE -
testcase_24 OLE -
権限があれば一括ダウンロードができます

ソースコード

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[1][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("S",S,"u",u,"v",v,t,"nt",nt,nx,ny,"TO",S|(1<<v))
                    dp[S|(1<<v)][v] = min(dp[S|(1<<v)][v], nt)
#print(dp)
ans = min(dp[(1<<N) - 1])
print(ans)
0