提出 #22891558

---

ソースコード 拡げる

# local test max score: 946037519
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,pos_dir,loop):
    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:
            if loop < SWITCH_NUM*2 and dir not in pos_dir:
                continue
            ty, tx = y+move[dir][0], x+move[dir][1]
            if not (0 <= ty <= H-1 and 0 <= tx <= W-1):
                continue
            cost = graph[ty][tx][dir]
            if seen[ty][tx] == False and d[y][x] + cost < d[ty][tx]:
                d[ty][tx] = d[y][x] + cost
                heappush(hq, (d[ty][tx], (ty, tx)))
                p[ty][tx] = [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 call_dijkstra(sy,sx,ty,tx,loop):
    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)
    dijkstra(dist,prev,sy,sx,possible_dir,loop)
    l, total_cost = get_path(prev,ty,tx)
    return [l,total_cost]

def calc_possible_dir(sy,sx,ty,tx):
    dy = ty-sy
    dx = tx-sx
    if dy < 0 and dx == 0: #U
        return ["U","R","L"]
    elif dy < 0 and dx > 0: #UR
        return ["U","R"]
    elif dy == 0 and dx > 0: #R
        return ["U","R","D"]
    elif dy > 0 and dx > 0: #DR
        return ["R","D"]
    elif dy > 0 and dx == 0: #D
        return ["R","D","L"]
    elif dy > 0 and dx < 0: #DL
        return ["D","L"]
    elif dy == 0 and dx < 0: #L
        return ["D","L","U"]
    elif dy < 0 and dx < 0: #UL
        return ["L","U"]

def reverse_dir(dir):
    if dir == "U":
        dir = "D"
    elif dir == "R":
        dir = "L"
    elif dir == "D":
        dir = "U"
    elif dir == "L":
        dir = "R"
    return dir

def update_graph_weight_ini(actual_cost,path,ty,tx,loop):
    weighted_cost = actual_cost//len(path)
    for dir in path[::-1]:
        sy = ty - move[dir][0]
        sx = tx - move[dir][1]
        graph[ty][tx][dir] = graph[sy][sx][reverse_dir(dir)] = weighted_cost
        ty,tx = sy,sx

def update_graph_weight_last(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
        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 = 100
SWITCH_NUM = 100
dirs = ["U","R","D","L"]
# {direction:cost}
graph = [[{"U":1, "R":1, "D":1, "L":1} for _ in range(W)] for _ in range(H)]
s_t_list = []
avg_actual_cost = 0

for i in range(1000):

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

    # calculate minimum path with dijkstra
    l,tmp_total_cost = call_dijkstra(sy,sx,ty,tx,i)
    path = "".join(l)
    print(path, flush=True)

    # update weights of the graph based on the given cost and the used path
    actual_cost = int(input())
    avg_actual_cost = actual_cost//len(path) if avg_actual_cost == 0 else (avg_actual_cost + actual_cost//len(path))//2

    # replace all graph weights which have the initial value(1)
    # with the average of actual costs of initial RECALC_NUM loops
    if i == RECALC_NUM:
        for y in range(H):
            for x in range(W):
                for dir in dirs:
                    graph[y][x][dir] = (graph[y][x][dir] + avg_actual_cost)//2 if graph[y][x][dir] != 1 else avg_actual_cost

    # # use initial RECALC_NUM inputs for increasing the accuracy of graph weight parameters
    # if i < RECALC_NUM:
    #     s_t_list.append(((sy,sx,ty,tx), actual_cost, tmp_total_cost))

    # if i == RECALC_NUM*3:
    #     for j in range(RECALC_NUM):
    #         sy2,sx2,ty2,tx2 = s_t_list[j][0]
    #         l2,tmp_total_cost2 = call_dijkstra(sy2,sx2,ty2,tx2,501)
    #         # if abs(s_t_list[j][1] - tmp_total_cost2) < s_t_list[j][1]*0.2:
    #         #     continue
    #         path2 = "".join(l2)
    #         update_graph_weight_ini(s_t_list[j][1],path2,ty2,tx2,i)
    #         # update_graph_weight_last(s_t_list[j][1],tmp_total_cost2,path2,ty2,tx2,i)

    # change the paramter tuning process for the first SWITCH_NUM loops and after that
    if i < SWITCH_NUM:
        update_graph_weight_ini(actual_cost,path,ty,tx,i)
    else:
        update_graph_weight_last(actual_cost,tmp_total_cost,path,ty,tx,i)

提出情報

ジャッジ結果