提出 #22983002

ソースコード 拡げる

# local test max score: 948246645
from heapq import heappush, heappop
inf=10**18
move = {"U":(-1,0), "R":(0,1), "D":(1,0), "L":(0,-1)}            
def dijkstra(d,p,pos_dir):
    hq = [(0, (sy,sx))] # (distance, node)
    seen = [[False]*W for _ in range(H)]
    while hq:
        y,x = heappop(hq)[1]
        seen[y][x] = True
        for dir in move:
            new_y, new_x = y+move[dir][0], x+move[dir][1]
            if dir not in pos_dir or not (0 <= new_y <= H-1 and 0 <= new_x <= W-1):
                continue
            cost = graph[new_y][new_x][dir]
            if seen[new_y][new_x] == False and d[y][x] + cost < d[new_y][new_x]:
                d[new_y][new_x] = d[y][x] + cost
                heappush(hq, (d[new_y][new_x], (new_y, new_x)))
                p[new_y][new_x] = [y,x]

def get_path(p,ty,tx):
    path = []
    total_cost = 0
    while not (ty == -1 and tx == -1):
        sy,sx = p[ty][tx]
        dy = ty-sy
        dx = tx-sx
        tmp = [k for k, v in move.items() if v == (dy,dx)]
        if tmp:
            dir = tmp[0]
            path.append(dir)
            total_cost += graph[ty][tx][dir]
        ty,tx = sy,sx
    path.reverse()
    return [path, total_cost]

def calc_possible_dir(sy,sx,ty,tx,loop):
    if loop >= SWITCH_NUM*3:
        return ["U","R","D","L"]

    flag = 1 if loop < SWITCH_NUM else 0  
    dy = ty-sy
    dx = tx-sx
    if dy < 0 and dx == 0: #U
        res = ["U"] if flag else ["U","R","L"]
    elif dy < 0 and dx > 0: #UR
        res = ["U","R"]
    elif dy == 0 and dx > 0: #R
        res = ["R"] if flag else ["U","R","D"]
    elif dy > 0 and dx > 0: #DR
        res = ["R","D"]
    elif dy > 0 and dx == 0: #D
        res = ["D"] if flag else ["R","D","L"]
    elif dy > 0 and dx < 0: #DL
        res = ["D","L"]
    elif dy == 0 and dx < 0: #L
        res = ["L"] if flag else ["D","L","U"]
    elif dy < 0 and dx < 0: #UL
        res = ["L","U"]
    return res

reverse_dir = {"U":"D", "R":"L", "D":"U", "L":"R"}
def update_graph_weight(actual_cost,tmp_total_cost,path,ty,tx,loop):
    if loop < SWITCH_NUM:
        edge_cost = actual_cost/len(path)
    for dir in path[::-1]:
        sy = ty - move[dir][0]
        sx = tx - move[dir][1]
        if loop < SWITCH_NUM:
            if graph[ty][tx][dir] == 1:
                graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = edge_cost
            else:
                graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir]*2 + edge_cost*3)/5
        else:
            weighted_cost = actual_cost * graph[ty][tx][dir]/tmp_total_cost
            if loop < SWITCH_NUM*10:
                graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir] + weighted_cost*2)/3
            else:
                graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir]*3 + weighted_cost*2)/5
        ty,tx = sy,sx

def update_graph_weight_adjust(actual_cost,tmp_total_cost,path,ty,tx,loop):
    for dir in path[::-1]:
        sy = ty - move[dir][0]
        sx = tx - move[dir][1]
        weighted_cost = actual_cost * graph[ty][tx][dir]/tmp_total_cost
        if loop == SWITCH_NUM*8-1:
            graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir] + weighted_cost*2)/3
        elif loop == SWITCH_NUM*12-1:
            graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir]*2 + weighted_cost*3)/5
        elif loop == SWITCH_NUM*16-1:
            graph[ty][tx][dir] = graph[sy][sx][reverse_dir[dir]] = (graph[ty][tx][dir] + weighted_cost)/2
        ty,tx = sy,sx

H = W = 30
RECALC_NUM = 50
SWITCH_NUM = 50
# {direction:cost}
graph = [[{"U":1, "R":1, "D":1, "L":1} for _ in range(W)] for _ in range(H)]
avg_actual_cost_all = 0
avg_actual_cost_grid = [[0]*3 for _ in range(3)]
used_path = []

for i in range(1000):

    # input position of start and goal
    sy,sx,ty,tx = map(int,input().split())

    # calculate minimum path with dijkstra
    dist = [[inf]*W for _ in range(H)]
    dist[sy][sx] = 0
    prev =[[[-1,-1]]*W for _ in range(H)]
    possible_dir = calc_possible_dir(sy,sx,ty,tx,i)
    dijkstra(dist,prev,possible_dir)
    l, tmp_total_cost = get_path(prev,ty,tx)
    path = "".join(l)
    print(path, flush=True)

    # get the actual cost(*0.9~1.1) of chosen path
    actual_cost = int(input())

    # update graph weights based on the chosen path and the actual cost in this loop
    # paramter tuning process varies depending on the loop count
    update_graph_weight(actual_cost,tmp_total_cost,path,ty,tx,i)

    # regularly adjust the graph weight by using already used path
    if i < SWITCH_NUM*16:
        used_path.append(((sy,sx,ty,tx), actual_cost, prev))

    if i == SWITCH_NUM*8-1 or i == SWITCH_NUM*12-1 or i == SWITCH_NUM*16-1:
        for p in used_path:
            sy2,sx2,ty2,tx2 = p[0]
            actual_cost2 = p[1]
            prev2 = p[2]
            path2,tmp_total_cost2 = get_path(prev2,ty2,tx2)
            update_graph_weight_adjust(actual_cost2,tmp_total_cost2,path2,ty2,tx2,i)

    # calculate the average of graph weights for each of 3x3 blocks
    if i < RECALC_NUM*2:
        edge_cost = actual_cost/len(path)
        avg_actual_cost_all = edge_cost if avg_actual_cost_all == 0 else (avg_actual_cost_all + edge_cost)/2
    # if i < RECALC_NUM*8:
    #     for y in range(H):
    #         for x in range(W):
    #             for dir in move:
    #                 if graph[y][x][dir] != 1:
    #                     avg_actual_cost_grid[y//10][x//10] = (graph[y][x][dir] + avg_actual_cost_grid[y//10][x//10])/2 if avg_actual_cost_grid[y//10][x//10] != 0 else graph[y][x][dir]

    # replace all graph weights which have the initial value(1)
    # with the calculated average of graph weights
    if i == RECALC_NUM-1 or i == RECALC_NUM*2-1:
        for y in range(H):
            for x in range(W):
                for dir in move:
                    graph[y][x][dir] = (graph[y][x][dir]*2 + avg_actual_cost_all)/3 if graph[y][x][dir] != 1 else avg_actual_cost_all
    # elif i == RECALC_NUM*5-1:
    #     for y in range(H):
    #         for x in range(W):
    #             for dir in move:
    #                 graph[y][x][dir] = (graph[y][x][dir]*3 + avg_actual_cost_grid[y//10][x//10])/4

提出情報

提出日時
問題 A - Shortest Path Queries
ユーザ otsuneko
言語 PyPy3 (7.3.0)
得点 93417969072
コード長 6419 Byte
結果 AC
実行時間 1732 ms
メモリ 159700 KiB

ジャッジ結果

セット名 test_ALL
得点 / 配点 93417969072 / 100000000000
結果
AC × 100
セット名 テストケース
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt
ケース名 結果 実行時間 メモリ
test_0000.txt AC 1625 ms 153344 KiB
test_0001.txt AC 1643 ms 153788 KiB
test_0002.txt AC 1679 ms 154304 KiB
test_0003.txt AC 1649 ms 152952 KiB
test_0004.txt AC 1655 ms 156392 KiB
test_0005.txt AC 1662 ms 153748 KiB
test_0006.txt AC 1638 ms 152912 KiB
test_0007.txt AC 1689 ms 155148 KiB
test_0008.txt AC 1639 ms 156444 KiB
test_0009.txt AC 1677 ms 153932 KiB
test_0010.txt AC 1619 ms 153924 KiB
test_0011.txt AC 1655 ms 155524 KiB
test_0012.txt AC 1596 ms 154600 KiB
test_0013.txt AC 1620 ms 153452 KiB
test_0014.txt AC 1663 ms 154944 KiB
test_0015.txt AC 1629 ms 153372 KiB
test_0016.txt AC 1679 ms 158280 KiB
test_0017.txt AC 1649 ms 154544 KiB
test_0018.txt AC 1661 ms 159700 KiB
test_0019.txt AC 1711 ms 154996 KiB
test_0020.txt AC 1666 ms 155344 KiB
test_0021.txt AC 1633 ms 152776 KiB
test_0022.txt AC 1693 ms 153660 KiB
test_0023.txt AC 1677 ms 155636 KiB
test_0024.txt AC 1676 ms 152796 KiB
test_0025.txt AC 1657 ms 153452 KiB
test_0026.txt AC 1621 ms 153240 KiB
test_0027.txt AC 1687 ms 154216 KiB
test_0028.txt AC 1653 ms 151388 KiB
test_0029.txt AC 1700 ms 154652 KiB
test_0030.txt AC 1687 ms 156064 KiB
test_0031.txt AC 1697 ms 153248 KiB
test_0032.txt AC 1702 ms 157544 KiB
test_0033.txt AC 1678 ms 153616 KiB
test_0034.txt AC 1691 ms 153712 KiB
test_0035.txt AC 1634 ms 156096 KiB
test_0036.txt AC 1631 ms 154624 KiB
test_0037.txt AC 1612 ms 153088 KiB
test_0038.txt AC 1633 ms 154068 KiB
test_0039.txt AC 1656 ms 154476 KiB
test_0040.txt AC 1641 ms 153216 KiB
test_0041.txt AC 1651 ms 155132 KiB
test_0042.txt AC 1677 ms 157188 KiB
test_0043.txt AC 1671 ms 157892 KiB
test_0044.txt AC 1657 ms 156588 KiB
test_0045.txt AC 1628 ms 154820 KiB
test_0046.txt AC 1612 ms 153056 KiB
test_0047.txt AC 1672 ms 156004 KiB
test_0048.txt AC 1673 ms 155744 KiB
test_0049.txt AC 1616 ms 155088 KiB
test_0050.txt AC 1644 ms 155960 KiB
test_0051.txt AC 1594 ms 152396 KiB
test_0052.txt AC 1682 ms 156208 KiB
test_0053.txt AC 1652 ms 154328 KiB
test_0054.txt AC 1691 ms 154180 KiB
test_0055.txt AC 1610 ms 153684 KiB
test_0056.txt AC 1643 ms 155520 KiB
test_0057.txt AC 1704 ms 154304 KiB
test_0058.txt AC 1652 ms 157292 KiB
test_0059.txt AC 1589 ms 152940 KiB
test_0060.txt AC 1666 ms 154176 KiB
test_0061.txt AC 1642 ms 153308 KiB
test_0062.txt AC 1653 ms 153676 KiB
test_0063.txt AC 1703 ms 157020 KiB
test_0064.txt AC 1695 ms 153036 KiB
test_0065.txt AC 1657 ms 154696 KiB
test_0066.txt AC 1675 ms 154924 KiB
test_0067.txt AC 1612 ms 153224 KiB
test_0068.txt AC 1613 ms 153888 KiB
test_0069.txt AC 1616 ms 154304 KiB
test_0070.txt AC 1665 ms 153756 KiB
test_0071.txt AC 1644 ms 153904 KiB
test_0072.txt AC 1629 ms 154856 KiB
test_0073.txt AC 1665 ms 154680 KiB
test_0074.txt AC 1642 ms 155040 KiB
test_0075.txt AC 1641 ms 153920 KiB
test_0076.txt AC 1699 ms 155056 KiB
test_0077.txt AC 1639 ms 153740 KiB
test_0078.txt AC 1689 ms 154352 KiB
test_0079.txt AC 1669 ms 154028 KiB
test_0080.txt AC 1624 ms 152460 KiB
test_0081.txt AC 1657 ms 153632 KiB
test_0082.txt AC 1666 ms 154500 KiB
test_0083.txt AC 1732 ms 154216 KiB
test_0084.txt AC 1638 ms 153300 KiB
test_0085.txt AC 1652 ms 152896 KiB
test_0086.txt AC 1646 ms 153992 KiB
test_0087.txt AC 1633 ms 155088 KiB
test_0088.txt AC 1583 ms 152908 KiB
test_0089.txt AC 1685 ms 154428 KiB
test_0090.txt AC 1620 ms 152828 KiB
test_0091.txt AC 1642 ms 153564 KiB
test_0092.txt AC 1613 ms 154876 KiB
test_0093.txt AC 1660 ms 155840 KiB
test_0094.txt AC 1695 ms 153804 KiB
test_0095.txt AC 1586 ms 153556 KiB
test_0096.txt AC 1599 ms 154516 KiB
test_0097.txt AC 1675 ms 157092 KiB
test_0098.txt AC 1627 ms 154284 KiB
test_0099.txt AC 1628 ms 153432 KiB