提出 #22967618

---

ソースコード 拡げる

# local test max score: 942918561
import random
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*3 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(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-1:
                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
        else:
            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 = 0
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 actual cost and the used path
    actual_cost = int(input())
    if i < RECALC_NUM*2:
        edge_cost = actual_cost/len(path)
        avg_actual_cost = edge_cost if avg_actual_cost == 0 else (avg_actual_cost + edge_cost)/2
        
    # replace all graph weights which have the initial value(1)
    # with the average of actual costs in initial RECALC_NUM loops
    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)/3 if graph[y][x][dir] != 1 else avg_actual_cost

    # adjust the graph weight of already used path regularly
    initial_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 j in range(len(initial_path)):
            sy2,sx2,ty2,tx2 = initial_path[j][0]
            prev2 = initial_path[j][2]
            path2,tmp_total_cost2 = get_path(prev2,ty2,tx2)
            update_graph_weight_adjust(initial_path[j][1],tmp_total_cost2,path2,ty2,tx2,i)

    # change the paramter tuning process depending on the loop count
    update_graph_weight(actual_cost,tmp_total_cost,path,ty,tx,i)

提出情報

ジャッジ結果