提出 #22923735

---

ソースコード 拡げる

# local test max score: 947159214
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 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]
        if graph[ty][tx][dir] == 1:
            graph[ty][tx][dir] = graph[sy][sx][reverse_dir(dir)] = weighted_cost
        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_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]*2 + weighted_cost*3)//5
        ty,tx = sy,sx

def calc_avg_actual_cost(actual_cost,path,sy,sx,ty,tx):
    sy_idx,sx_idx = sy*2//H,sx*2//W
    ty_idx,tx_idx = ty*2//H,tx*2//W

    edge_cost = actual_cost//len(path)
    if False:#[sy_idx, sx_idx] == [ty_idx, tx_idx]:
        avg_actual_cost[sy_idx][sx_idx] = edge_cost if avg_actual_cost[sy_idx][sx_idx] == 0 else (avg_actual_cost[sy_idx][sx_idx] + edge_cost)//2
        avg_actual_cost[ty_idx][tx_idx] = edge_cost if avg_actual_cost[ty_idx][tx_idx] == 0 else (avg_actual_cost[ty_idx][tx_idx] + edge_cost)//2
    else:
        for y_idx in range(2):
            for x_idx in range(2):
                avg_actual_cost[y_idx][x_idx] = edge_cost if avg_actual_cost[y_idx][x_idx] == 0 else (avg_actual_cost[y_idx][x_idx] + edge_cost)//2

H = W = 30
RECALC_NUM = 100
SWITCH_NUM = 100
# {direction:cost}
graph = [[{"U":1, "R":1, "D":1, "L":1} for _ in range(W)] for _ in range(H)]
avg_actual_cost = [[0]*2 for _ in range(2)]
initial_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)
    dijkstra(dist,prev,sy,sx,possible_dir,i)
    l, tmp_total_cost = get_path(prev,ty,tx)
    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())
    if i <= RECALC_NUM*2:
        calc_avg_actual_cost(actual_cost,path,sy,sx,ty,tx)

    # 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 move:
                    graph[y][x][dir] = (graph[y][x][dir]*2 + avg_actual_cost[y*2//H][x*2//W])//3 if graph[y][x][dir] != 1 else avg_actual_cost[y*2//H][x*2//W]

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

    # if i and i == RECALC_NUM*2:
    #     for j in range(RECALC_NUM):
    #         sy2,sx2,ty2,tx2 = initial_path[j][0]
    #         l2,tmp_total_cost2 = get_path(initial_path[j][2],ty2,tx2)
    #         update_graph_weight_last(initial_path[j][1],tmp_total_cost2,initial_path[j][3],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)

提出情報

ジャッジ結果