結果

問題 No.1413 Dynamic Sushi
ユーザー ygd.ygd.
提出日時 2021-03-04 00:40:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,569 ms / 4,000 ms
コード長 2,326 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 81,576 KB
最終ジャッジ日時 2024-10-03 22:13:59
合計ジャッジ時間 49,309 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
64,256 KB
testcase_01 AC 39 ms
52,736 KB
testcase_02 AC 38 ms
52,736 KB
testcase_03 AC 43 ms
53,888 KB
testcase_04 AC 1,267 ms
80,232 KB
testcase_05 AC 2,478 ms
80,628 KB
testcase_06 AC 2,504 ms
80,652 KB
testcase_07 AC 2,504 ms
80,380 KB
testcase_08 AC 2,555 ms
81,144 KB
testcase_09 AC 2,483 ms
80,556 KB
testcase_10 AC 2,504 ms
80,784 KB
testcase_11 AC 2,533 ms
80,608 KB
testcase_12 AC 2,566 ms
81,448 KB
testcase_13 AC 2,012 ms
80,120 KB
testcase_14 AC 2,510 ms
80,304 KB
testcase_15 AC 2,537 ms
80,632 KB
testcase_16 AC 2,529 ms
80,608 KB
testcase_17 AC 2,542 ms
80,556 KB
testcase_18 AC 2,533 ms
80,520 KB
testcase_19 AC 2,532 ms
79,868 KB
testcase_20 AC 1,202 ms
79,620 KB
testcase_21 AC 127 ms
76,928 KB
testcase_22 AC 2,465 ms
80,620 KB
testcase_23 AC 2,523 ms
81,576 KB
testcase_24 AC 2,569 ms
80,480 KB
権限があれば一括ダウンロードができます

ソースコード

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(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