結果

問題 No.1413 Dynamic Sushi
ユーザー ygd.ygd.
提出日時 2021-03-04 00:40:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,515 ms / 4,000 ms
コード長 2,326 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 81,828 KB
最終ジャッジ日時 2024-04-14 19:58:04
合計ジャッジ時間 48,109 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
66,300 KB
testcase_01 AC 37 ms
54,184 KB
testcase_02 AC 37 ms
53,216 KB
testcase_03 AC 39 ms
54,732 KB
testcase_04 AC 1,207 ms
80,236 KB
testcase_05 AC 2,427 ms
80,548 KB
testcase_06 AC 2,456 ms
80,524 KB
testcase_07 AC 2,482 ms
80,884 KB
testcase_08 AC 2,505 ms
81,276 KB
testcase_09 AC 2,460 ms
80,944 KB
testcase_10 AC 2,462 ms
80,656 KB
testcase_11 AC 2,459 ms
80,608 KB
testcase_12 AC 2,515 ms
81,712 KB
testcase_13 AC 1,926 ms
80,076 KB
testcase_14 AC 2,486 ms
80,556 KB
testcase_15 AC 2,494 ms
80,512 KB
testcase_16 AC 2,470 ms
80,992 KB
testcase_17 AC 2,456 ms
80,584 KB
testcase_18 AC 2,493 ms
80,524 KB
testcase_19 AC 2,479 ms
80,256 KB
testcase_20 AC 1,186 ms
79,624 KB
testcase_21 AC 124 ms
77,172 KB
testcase_22 AC 2,421 ms
80,760 KB
testcase_23 AC 2,485 ms
81,828 KB
testcase_24 AC 2,499 ms
80,860 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