AtCoder AHC002 個人的メモ

所感

1,088,476点で641位でした
ahc001が1232位だったので，かなり進歩しているはず

A - Walking on Tiles

最終的には時間の限り乱択した

最初は現在地点の上下左右の最も大きい得点のマスへの移動を繰り返す貪欲法を実装した．
サンプルと同じ結果が得られる．

貪欲法

def move_adjacent_max(y: int, x: int, score: int, history: list):
    """現在地点(y,x)から上下左右の4方向の内，最大の得点の方向へ移動し続ける．

    Args:
        y (int): 現在地点のy座標
        x (int): 現在地点のx座標
        score (int): 現在の得点
        history (list): 現在地点までの移動経路

    Returns:
        res[0] (int): 終了時のscore
        res[1] (list): 終了時のhistory
    """
    if tile[y][x] in seen:
        history.pop()
        score -= points[y][x]
        return score, history

    seen.add(tile[y][x])
    can = (-1, - 1, 0, "")
    for dy, dx, move in ((-1, 0, "U"), (1, 0, "D"), (0, -1, "L"), (0, 1, "R")):
        ny = y + dy
        nx = x + dx
        if not 0 <= ny < H or not 0 <= nx < W or tile[ny][nx] in seen:
            continue
        if can[2] < points[ny][nx]:
            can = (ny, nx, points[ny][nx], move)

    res = move_adjacent_max(can[0], can[1], score + can[2], list(history + [can[3]]))
    seen.discard(tile[y][x])

    return res


H, W = 50, 50
sy, sx = map(int, input().split())
tile = [list(map(int, input().split())) for _ in range(H)]
points = [list(map(int, input().split())) for _ in range(H)]

seen = set()
score, history = move_adjacent_max(sy, sx, points[sy][sx], [])

print("".join(str(x) for x in history))

その後，移動可能な方向を制限してみた．

移動方向を制限した貪欲法

from itertools import permutations


def move_adjacent_max(y: int, x: int, score: int, history: list, lst: list):
    """現在地点(y,x)からlstで定義された方向の内，最大の得点の方向へ移動し続ける．

    Args:
        y (int): 現在地点のy座標
        x (int): 現在地点のx座標
        score (int): 現在の得点
        history (list): 現在地点までの移動経路
        lst (list): 移動可能な方向

    Returns:
        res[0] (int): 終了時のscore
        res[1] (list): 終了時のhistory
    """
    if tile[y][x] in seen:
        history.pop()
        score -= points[y][x]
        return score, history

    seen.add(tile[y][x])
    can = (-1, - 1, 0, "")
    for dy, dx, move in lst:
        ny = y + dy
        nx = x + dx
        if not move or not 0 <= ny < H or not 0 <= nx < W or tile[ny][nx] in seen:
            continue
        if can[2] < points[ny][nx]:
            can = (ny, nx, points[ny][nx], move)

    res = move_adjacent_max(can[0], can[1], score + can[2], list(history + [can[3]]), lst)
    seen.discard(tile[y][x])
    return res


H, W = 50, 50
sy, sx = map(int, input().split())
tile = [list(map(int, input().split())) for _ in range(H)]
points = [list(map(int, input().split())) for _ in range(H)]

score, history = 0, ""
for lst in permutations(((-1, 0, "U"), (1, 0, "D"), (0, -1, "L"), (0, 1, "R"), (0, 0, "")), 4):
    seen = set()
    tmp = move_adjacent_max(sy, sx, points[sy][sx], [], lst)
    if score < tmp[0]:
        score, history = tmp

print("".join(str(x) for x in history))

その後，より良い移動方向の選択方法を考えたが思いつかず．
実行時間に余裕があったので，時間の限り移動方向をランダムに選択する探索を実装してみる．
この方法が上記2つよりも明らかに優秀な結果を出したので，上記の方法は不採用にして乱択のみにした．

from random import randint
from time import time


def rand_norec(y: int, x: int, seen: set):
    """スタート地点からランダムな方向に進み続ける．進めなくなったら終わり．

    Args:
        y (int): 初期地点のy座標
        x (int): 初期地点のx座標
        seen (set): 通ったタイルの色を集合でメモ

    Returns:
        score (int): 終了時の得点
        history (list): 移動経路(解)
    """
    score, history = points[y][x], []
    while True:
        if time() - start > 1.8:
            return score, history

        seen.add(tile[y][x])
        lst = []
        for dy, dx, move in migration:
            ny = y + dy
            nx = x + dx
            if not 0 <= ny < H or not 0 <= nx < W or tile[ny][nx] in seen:
                continue
            res = ny, nx, points[ny][nx], move
            lst.append(res)

        if not lst:
            break

        can = lst[randint(0, len(lst) - 1)]
        score += can[2]
        history.append(can[3])
        y, x = can[0], can[1]

    return score, history


def output_ans():
    ans = "".join(str(x) for x in history)
    return ans


start = time()
H, W = 50, 50
sy, sx = map(int, input().split())
tile = [list(map(int, input().split())) for _ in range(H)]
points = [list(map(int, input().split())) for _ in range(H)]

migration = [(-1, 0, "U"), (1, 0, "D"), (0, -1, "L"), (0, 1, "R")]
score = 0
history = []

while time() - start < 1.8:
    tmp = rand_norec(sy, sx, set())
    if score < tmp[0]:
        score, history = tmp

print(output_ans())