Problem:


Problem B: Carrot Tour 

うさぎがある国を旅行している. この国には1 からn の番号がついたn 個の都市があり, うさぎは今都市1にいる. 都市i は座標平面上の1 点(xi, yi) とみなす.

うさぎは以下の条件をみたすように旅をする.

 移動経路は折れ線であり, その各部分は異なる2 都市を結ぶ線分でなければならない.

 移動経路の全長はr 以下でなければならない. 経路のうち重なった部分も, 通った回数分数える.

 移動する方向が変わるとき, 曲がる角度は&theta; 以下でなければならない. 最初の移動方向に制限はない.

うさぎがある都市から別の都市へ移動をすると, 移動先の都市でニンジンを1 本もらえる. 同じ都市を複数回訪れることは可能であり, 訪れるたびにニンジンをもらえる. うさぎがこの旅で手に入れることのできるニンジンの本数の最大値を求めよ.

Input

入力の一行目には一つの整数n が, 二行目には二つの実数r, &theta; がスペースで区切られて与えられる.

1 ≤ n ≤ 20

0 < r < 104

0&deg; < &theta; < 180&deg;

続くn 行には, 整数xi, yi がスペースで区切られて与えられる

-10 000 ≤ xi, yi ≤ 10 000

r, &theta; を&plusmn;10−3 以内で変化させても答えは変わらない.

どの2 つの都市の位置も異なる.

Output

うさぎがこの旅で手に入れることのできるニンジンの本数の最大値を一行に出力せよ.

Sample Input 1

5
100.1 90.1
0 0
0 10
5 5
10 0
10 10

Sample Output 1

10



Sample input:
5
100.1 90.1
0 0
0 10
5 5
10 0
10 10


Sample output:
10

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f():
        n = I()
        r,t = LF()
        a = [LI() for _ in range(n)]
        d = []
        for i in range(n):
            di = []
            ax,ay = a[i]
            for j in range(n):
                if i == j:
                    di.append(0)
                    continue
                bx,by = a[j]
                di.append(math.atan2(bx-ax,by-ay) / math.pi * 180)
            d.append(di)
        ky = []
        for i in range(n):
            ki = []
            ax,ay = a[i]
            for j in range(n):
                bx,by = a[j]
                ki.append(pow(pow(ax-bx, 2) + pow(ay-by, 2), 0.5))
            ky.append(ki)
        e = collections.defaultdict(list)
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                dij = d[i][j]
                dj = d[j]
                for k in range(n):
                    if k == j:
                        continue
                    djk = dj[k]
                    if abs(dij-djk) <= t or 360 - abs(dij-djk) <= t:
                        e[(i,j)].append(((j,k), ky[j][k]))

        def search():
            d = collections.defaultdict(lambda: inf)
            q = []
            for j in range(1, n):
                s = (0,j,0)
                d[s] = 0
                heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[(u[0],u[1])]:
                    uv = (uv[0],uv[1],u[2]+1)
                    if v[uv]:
                        continue
                    vd = k + ud
                    if vd > r:
                        continue
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        d = search()

        return max(map(lambda x: x[2], d.keys()))

    while True:
        rr.append(f())
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f():
        n = I()
        r,t = LF()
        a = [LI() for _ in range(n)]
        d = []
        for i in range(n):
            di = []
            ax,ay = a[i]
            for j in range(n):
                if i == j:
                    di.append(0)
                    continue
                bx,by = a[j]
                di.append(math.atan2(bx-ax,by-ay) / math.pi * 180)
            d.append(di)
        ky = []
        for i in range(n):
            ki = []
            ax,ay = a[i]
            for j in range(n):
                bx,by = a[j]
                ki.append(pow(pow(ax-bx, 2) + pow(ay-by, 2), 0.5))
            ky.append(ki)
        e = collections.defaultdict(list)
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                dij = d[i][j]
                dj = d[j]
                for k in range(n):
                    if k == j:
                        continue
                    djk = dj[k]
                    if abs(dij-djk) <= t or 360 - abs(dij-djk) <= t:
                        e[(i,j)].append(((j,k), ky[j][k]))

        def search():
            d = collections.defaultdict(lambda: inf)
            q = []
            for j in range(1, n):
                k = ky[0][j]
                if k > r:
                    continue
                s = (0,j,1)
                d[s] = k
                heapq.heappush(q, (k, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[(u[0],u[1])]:
                    uv = (uv[0],uv[1],u[2]+1)
                    if v[uv]:
                        continue
                    vd = k + ud
                    if vd > r:
                        continue
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        d = search()
        if len(d) == 0:
            return 0

        return max(map(lambda x: x[2], d.keys()))

    while True:
        rr.append(f())
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq

EPS = 1e-10
INF = 999999999

def dot(a, b):
    return a[0]*b[0] + a[1]*b[1]
def norm(a):
    return math.hypot(a[0], a[1])
def sub(a, b):
    return (a[0]-b[0], a[1]-b[1])
def get_angle(a, b):
    return math.acos(dot(a,b) / (norm(a) * norm(b)))

def main():
    n = int(sys.stdin.readline())
    r, degree = map(float, sys.stdin.readline().split())
    rad = math.radians(degree)
    nodes = []
    for i in range(n):
        x,y = map(int, sys.stdin.readline().split())
        nodes.append( (x,y) )

    edges = {}
    # ????????????????????¨???
    for i in range(n): # ?????¨??°
        for j in range(n): # ?????????
            if i == j:
                continue
            for k in range(n): # ?¬??????´???
                if i == k or j == k:
                    continue
                angle = get_angle( sub(nodes[k], nodes[i]), sub(nodes[i], nodes[j]) )
                if angle <= rad + EPS:
                    if i not in edges:
                        edges[i] = {}
                    if j not in edges[i]:
                        edges[i][j] = []
                    edges[i][j].append( k )

    # cost
    costs = {}
    for i in range(n):
        costs[i] = {}
        for j in range(n):
            if i == j:
                costs[i][j] = INF
            else:
                costs[i][j] = norm(sub(nodes[i], nodes[j]))

    # [?????????????????°k][?????¨??°i][??????j]
    dp = [[[INF for j in range(n)] for i in range(n)] for k in range(10001)]

    pq = []
    heapq.heapify(pq)
    # init
    for k in range(n):
        if costs[0][k] <= r + EPS:
            dp[1][k][0] = costs[0][k]
            heapq.heappush(pq, (costs[0][k], (1,k,0))) # (cost, (????????????, ?????¨??°, ??????))

    while len(pq) > 0:
        curr_cost,state = heapq.heappop(pq)
        curr_carrot, curr, prev = state

        # ?????????????????¶?????????????????????
        if curr not in edges:
            continue
        if prev not in edges[curr]:
            continue

        for t in edges[curr][prev]:
            next_cost = curr_cost + costs[curr][t]
            if dp[curr_carrot + 1][t][curr] > next_cost and next_cost <= r + EPS:
                dp[curr_carrot + 1][t][curr] = next_cost
                heapq.heappush(pq, (next_cost, (curr_carrot + 1, t, curr)))

    ans = 0
    for k in range(10001):
        for i in range(n):
            for j in range(n):
                if dp[k][i][j] != INF:
                    ans = max(ans, k)

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f():
        n = I()
        r,t = LF()
        a = [LI() for _ in range(n)]
        d = {}
        M = 32
        for i in range(n):
            ax,ay = a[i]
            for j in range(n):
                if i == j:
                    continue
                bx,by = a[j]
                d[i*M+j] = math.atan2(bx-ax,by-ay) / math.pi * 180
        ky = {}
        for i in range(n):
            ax,ay = a[i]
            for j in range(n):
                bx,by = a[j]
                ky[i*M+j] = pow(pow(ax-bx, 2) + pow(ay-by, 2), 0.5)
        e = collections.defaultdict(list)
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                ij = i*M+j
                dij = d[ij]
                for k in range(n):
                    if k == j:
                        continue
                    jk = j*M+k
                    djk = d[jk]
                    if abs(dij-djk) <= t or 360 - abs(dij-djk) <= t:
                        e[(i,j)].append(((j,k), ky[jk]))

        def search():
            res = 0
            dp = [[None]*n for _ in range(n)]
            for j in range(1, n):
                k = ky[j]
                if k > r:
                    continue
                s = (j,1)
                res = 1
                dp[0][j] = k
            if res == 0:
                return 0
            while True:
                wf = False
                nd = [[None]*n for _ in range(n)]
                for i in range(n):
                    for j in range(n):
                        if dp[i][j] is None:
                            continue
                        dij = dp[i][j]
                        for nn,k in e[(i,j)]:
                            nk = dij + k
                            if nk > r or (not nd[j][nn[1]] is None and nd[j][nn[1]] < nk):
                                continue
                            nd[j][nn[1]] = nk
                            wf = True
                if wf:
                    res += 1
                    dp = nd
                else:
                    break
            return res

        return search()

    while True:
        rr.append(f())
        break

    return '\n'.join(map(str,rr))


print(main())