AHC026参加記 - まだタイトルない

こんにちは

AHC026に参加してきました！

212th/1644で青パフォでした（入水しそこねた・・・・・

今回はちょっと手短に振り返ります

課題の確認

問題はcontest page参照

ソリティアと言ってる参加者が多くたしかにそんな感じだと思います。

考察

取り除くアイテムは200個、操作は5000回できる
- 毎回上に乗ってるものをどかしてから取り除いても400回なので結構余裕
- 1つ取り除くのに25回移動させられるので制約違反は気にしなくて良さそう
目的の数字の上にN個荷物が乗っていたらそれを撤去するにはNの体力消費をすればできる
- 何回に分けてもN消費することは変わらないというのは多分ポイント

とりあえず愚直に上に乗っかってる荷物を隣に移す

code

from collections import defaultdict
N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

def get_over_n(n):
    # nの上に置かれた数字と箱の番号
    for m in range(M):
        for i in range(len(B[m])):
            if B[m][i] != n:continue
            if i == (len(B[m])-1):
                return 0, m
            else:
                return B[m][i+1], m

def move(n, cur_b, nxt_b):
    #nを箱bから箱bに移す
    idx = -1
    for i in range(len(B[cur_b])):
        if B[cur_b][i] == n:
            idx = i
    B[nxt_b] = B[nxt_b]+B[cur_b][idx:]
    B[cur_b] = B[cur_b][:idx]


for n in range(1,N+1):
    over_n, cur = get_over_n(n)
    # 上に乗ってる荷物をどける
    if over_n != 0:
        nxt = (cur+1)%M
        move(over_n, cur, nxt)
        print(over_n, nxt+1)
    print(n,0)
    B[cur].remove(n)

nxt = (cur+1)%Mで隣の箱の番号を計算してそのまま移します

これで1,221,582で710位くらいで茶パフォです

自分以外のボックスで一番使われるのが遅いボックスに移動させる

code

def get_next_box(n):
    # 次移動させるボックスを計算する
    s = set(range(M))
    s.remove(box_dict[n])
    while len(s)>1 and n < 200:
        n += 1
        idx = box_dict[n]
        if idx in s:
            s.remove(idx)
    l = list(s)
    return l[0]

こんな感じの関数で直近で使わなそうなボックスをとってきます。whileの条件を考えるのとsetの中に要素が複数残る可能性があることに注意が必要です

これをすると 1,356,657で426位、水パフォまで上がります

同じスコアの人めちゃくちゃいたけど同じ方針？？？？

移動させるときに直近で使いそうなものが上に来るように入れ替えてみる

code

# N個のダンボール
# M個の山
# 最大5000回作業できる
# - 1個の箱を取り出すために25回位操作してもいいと言える
from collections import defaultdict
import numpy as np
N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]
D = 2 # 何個移動を考える？

# nはboxmにある
box_dict = defaultdict(int)
for i in range(M):
    for v in B[i]:
        box_dict[v] = i

def get_over_n(n):
    # nの上に置かれた数字と箱の番号(0-index)
    for m in range(M):
        for i in range(len(B[m])):
            if B[m][i] != n:continue
            if i == (len(B[m])-1):
                return 0, m
            else:
                return B[m][i+1], m

def get_best_sep_idx(l):
    # 2回に分けて移動させる時、どこで区切るといいか求める
    sorted_l = sorted(l)
    best = 10**18
    best_idx = -1
    for i in range(len(l)):
        tmp = l[i:]+l[:i]
        cnt = 0
        for n in range(D):
            _ = np.argmin(tmp)
            cnt += len(tmp) - _ - 1
            tmp.remove(tmp[_])
        if best > cnt:
            best = cnt
            best_idx = i
    return best_idx

def move2(n, cur_b, nxt_b):
    #nを箱cur_bから箱nxt_bに移す
    idx = -1
    for i in range(len(B[cur_b])):
        if B[cur_b][i] == n:
            idx = i
    move_l = B[cur_b][idx:]
    # dictionary更新
    for v in move_l:
        box_dict[v] = nxt_b

    if len(move_l) >= D:
        best_idx = get_best_sep_idx(move_l)
        if best_idx == 0:
            B[nxt_b] = B[nxt_b]+move_l
            B[cur_b] = B[cur_b][:idx]
            print(move_l[0],nxt_b+1)
        else:
            print(move_l[best_idx],nxt_b+1)
            print(move_l[0],nxt_b+1)
            move_l = move_l[best_idx:] + move_l[:best_idx]
            B[nxt_b] = B[nxt_b]+move_l
            B[cur_b] = B[cur_b][:idx]
    else:
        B[nxt_b] = B[nxt_b]+move_l
        B[cur_b] = B[cur_b][:idx]
        print(move_l[0],nxt_b+1)

def get_next_box(n):
    # 次移動させるボックスを計算する
    s = set(range(M))
    s.remove(box_dict[n])
    while len(s)>1 and n < 200:
        n += 1
        idx = box_dict[n]
        if idx in s:
            s.remove(idx)
    l = list(s)
    return l[0]

for n in range(1,N+1):
    over_n, cur = get_over_n(n)
    # 上に乗ってる荷物をどける
    if over_n != 0:
        nxt = get_next_box(n)
        move2(over_n, cur, nxt)
    print(n,0)
    B[cur].remove(n)