提出 #22850265

---

ソースコード 拡げる

# local test max score: 916839889
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,sy,sx):
    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 key in move:
            new_y, new_x = y+move[key][0], x+move[key][1]
            if not (0 <= new_y <= H-1 and 0 <= new_x <= W-1):
                continue
            cost = graph[new_y][new_x][key][1]
            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 reverse_dir(dir):
    if dir == "U":
        dir = "D"
    elif dir == "D":
        dir = "U"
    elif dir == "L":
        dir = "R"
    elif dir == "R":
        dir = "L"
    return dir

def get_path(ty,tx):
    path = []
    total_cost = 0
    t = [ty,tx]
    while t != [-1,-1]:
        s = prev[t[0]][t[1]]
        y = t[0]-s[0]
        x = t[1]-s[1]
        tmp = [k for k, v in move.items() if v == (y,x)]
        if tmp:
            path.append(tmp[0])
            graph[t[0]][t[1]][tmp[0]][0] += 1
            graph[y][x][reverse_dir(tmp[0])][0] += 1
            total_cost += graph[t[0]][t[1]][tmp[0]][1]
        t = s
    path.reverse()
    return [path, total_cost]

def update_graph_weight_ini(actual_cost,path,ty,tx):
    t = [ty,tx]
    for p in path[::-1]:
        y = t[0] - move[p][0]
        x = t[1] - move[p][1]
        graph[t[0]][t[1]][p][1] = graph[y][x][reverse_dir(p)][1] = actual_cost//len(path)
        # count = graph[t[0]][t[1]][p][0]
        # old_cost = graph[t[0]][t[1]][p][1]
        # graph[t[0]][t[1]][p][1] = (old_cost*count + actual_cost//len(path))//(count+1)
        # count = graph[y][x][reverse_dir(p)][0]
        # old_cost = graph[y][x][reverse_dir(p)][1]
        # graph[y][x][reverse_dir(p)][1] = (old_cost*count + actual_cost//len(path))//(count+1)
        t = [y,x]

def update_graph_weight_last(actual_cost,tmp_total_cost,path,ty,tx):
    t = [ty,tx]
    for p in path[::-1]:
        y = t[0] - move[p][0]
        x = t[1] - move[p][1]
        weighted_cost = actual_cost * graph[t[0]][t[1]][p][1]//tmp_total_cost
        graph[t[0]][t[1]][p][1] = graph[y][x][reverse_dir(p)][1] = (graph[t[0]][t[1]][p][1] + weighted_cost)//2
        t = [y,x]

H = W = 30
# {direction:[count, cost]}
graph = [[{"U":[1,1], "R":[1,1], "D":[1,1], "L":[1,1]} for _ in range(W)] for _ in range(H)]

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)]
    dijkstra(dist,prev,sy,sx)
    l, tmp_total_cost = get_path(ty,tx)
    path = "".join(l)
    print(path, flush=True)

    # update weights of the graph based on the given cost and the used path
    # change the paramter tuning process for the first quarter and after that.
    actual_cost = int(input())
    if i < 250:
        update_graph_weight_ini(actual_cost,path,ty,tx)
    else:
        update_graph_weight_last(actual_cost,tmp_total_cost,path,ty,tx)

提出情報

ジャッジ結果