[python]HACK TO THE FUTURE 2021 予選 個人的メモ[Atcoder]

HACK TO THE FUTURE 2021 予選

所感

とりあえず，4時間ぐらい取り組んだ

A - カードの回収

自分の提出

最初に提出したコード
カードの番号順に愚直に回収していく
サンプルと一致する結果が出る

height = 20
wide = 20
num_card = 100
card = [list(map(int, input().split())) for _ in range(num_card)]

ans = ""
now = 0, 0
for i in range(num_card):
    h, w = card[i]
    move = h - now[0], w - now[1]

    res = "U" if move[0] < 0 else "D"
    ans += res * abs(move[0])

    res = "L" if move[1] < 0 else "R"
    ans += res * abs(move[1])

    ans += "I"
    now = h, w

print(ans)

次に提出したコード
次に山札に積みたい番号に連続する番号を移動する途中に，移動回数が増えることなく寄れるならついでに寄れば効率が良くなりそう

from collections import deque


def search_card_coordinate(i: int):
    """i番のカードの座標をgridから探索して座標を返す"""
    for x in range(height):
        if i in grid[x]:
            return x, grid[x].index(i)
    return False


def by_the_way(i: int, start: tuple, goal: tuple):
    """i番のカードをついでに拾っていけるかを判定，真なら座標を返す"""
    res = search_card_coordinate(i)
    if res is False:
        return False
    if not (start[0] <= res[0] <= goal[0] or goal[0] <= res[0] <= start[0]):
        return False
    if not (start[1] <= res[1] <= goal[1] or goal[1] <= res[1] <= start[1]):
        return False
    return res


def move_to(start: tuple, goal: tuple):
    """startの座標からgoalの座標までの移動に必要な文字列を出力"""
    res = ""
    move = goal[0] - start[0], goal[1] - start[1]
    direction = "U" if move[0] < 0 else "D"
    res += direction * abs(move[0])
    direction = "L" if move[1] < 0 else "R"
    res += direction * abs(move[1])

    return res


def search_blank_coordinate(start: tuple, limit: tuple):
    """(x, y)から最も近い空きますをBFSで探索し，座標を返す"""
    queue = deque([start])
    while queue:
        x, y = queue.popleft()
        if (x, y) == limit:
            return False
        if grid[x][y] == -1:
            return x, y

        if limit[0] - x > 0:
            queue.append((x + 1, y))
        elif limit[0] - x < 0:
            queue.append((x - 1, y))

        if limit[1] - y > 0:
            queue.append((x, y + 1))
        elif limit[1] - y < 0:
            queue.append((x, y - 1))


height = 20
wide = 20
num_card = 100
grid = [[-1] * wide for _ in range(height)]
for i in range(num_card):
    x, y = map(int, input().split())
    grid[x][y] = i

ans = ""
now = 0, 0
for i in range(num_card):
    # とるカード(目的のカードとついでにとれるカード)の座標をpick_lstに記録
    pick_lst = [search_card_coordinate(i)]
    # 最初の目的のカードを拾うために，目的カード周辺についでカードをぶちまける
    # ついでカードの枚数と同じ数の空きマスがぶちまけるために必要
    blank_lst = [pick_lst[0]]
    tmp_now = now
    for j in range(1, num_card - i):
        res = by_the_way(i + j, tmp_now, pick_lst[-1])
        if res is False:
            break
        # ついでカード候補が十分に目的カードに近ければ(目的カード付近の空きマスが無い)拾う必要は無い
        blank = search_blank_coordinate(blank_lst[-1], res)
        if blank is False:
            break
        pick_lst.append(res)
        blank_lst.append(blank)
        tmp_now = res
    blank_lst.pop(0)

    # 文字列の生成
    n = len(blank_lst)
    for goal in pick_lst[::-1]:
        if goal == pick_lst[0]:
            for destination in blank_lst[::-1]:
                ans += move_to(now, destination) + "O"
                grid[destination[0]][destination[1]] = i + n
                n -= 1
                now = destination
        ans += move_to(now, goal) + "I"
        grid[goal[0]][goal[1]] = -1
        now = goal

print(ans)

コンテスト後に解説配信見て上のコードに追加した関数
初期配置のカードをすべて回収して，左下の$10\times 10$の範囲に再配置する

def initialize(ans: str):
    """初期配置のカードを1か所に集約"""
    # とりあえず左上から右下まで行って全部拾って左下から四角の範囲に配置
    # 回収
    queue = deque([])
    for x in range(height):
        if x != 0:
            ans += "D"
        for w in range(wide):
            if x % 2:
                y = wide - w - 1
                ans += "L" if w else ""
            else:
                y = w
                ans += "R" if w else ""

            if grid[x][y] != -1:
                ans += "I"
                queue.append(grid[x][y])
                grid[x][y] = -1

    # 再配置，現在地は左下
    re_height = 10
    re_wide = 10
    for x in range(height - 1, re_height - 1, -1):
        if x != height - 1:
            ans += "U"
        for w in range(re_wide):
            if x % 2:
                y = w
                ans += "R" if y != 0 else ""
            else:
                y = re_wide - w - 1
                ans += "L" if y != re_wide - 1 else ""
            ans += "O"
            grid[x][y] = queue.pop()
    return ans

解説配信の話

解説配信で圧縮とかの話してた
$20\times 20$の盤面は広すぎるから，$10\times 10$の盤面にカードをまとめる
圧縮するって発想はあったけど，それで手数が減るとは思わなかった

• 回収時
  巡回セールスマン問題で良い解が得られる
  焼きなましとか2-optとかでより最適化できるらしい

• 配置時
  あまり最適化できなさそう
  圧縮するとこには100マス中75マスぐらい空きがある
  端から適当に置いてっても100解の操作で済むので余り最適化の余地が無い

• その他
  配置と再回収を同時に考えることで配置の効率は下がっても再回収の効率は上がる
  それで全体として最適化される
  良い問題らしい

• マラソンtips
  とりあえず答えを出す→もっと良い方法があったらそっちに変える