PAST3K
from 第三回 アルゴリズム実技検定
PAST3K
複数の机の上に複数の数値の書かれた箱があって、命令に従ってあっちこっち動かす問題。
机も箱も20万個あって、命令も20万個ある。
ひとつの命令の実行が十分軽くないと時間オーバーする。
Pythonのリストを配列的に使って、データ構造の意味のリストを作る。 リンクトリスト
これは普通にオブジェクトと参照でやった場合にオーバーヘッドで時間切れになるのを恐れたのと、コードの見た目の違いであって本質的には変わらないよなと思ったから。
長さN+1の配列を4つ用意して、それぞれ「箱iの下の箱」「箱iの上の箱」「机iの一番下の箱」「机iの一番上の箱」を意味している。
N+1するのは問題条件が1オリジンだから。
間違えずに1ずらして入出力するより、気にせず使える状況を作った。
0をnullの意味に使えるしね。
問題Eではそれをやらなかったので4箇所でずらしが必要になってる。
デバッグのためにわかりやすい表示をする関数を用意してあとは素朴に実装する。
pythonN, Q = [int(x) for x in input().split()]
prev = [-table for table in range(N + 1)]
next = [0] * (N + 1)
top = [table for table in range(N + 1)]
bottom = [table for table in range(N + 1)]
def debugPrint():
blocks = [[] for i in range(N + 1)]
for table in range(1, N + 1):
cur = bottom[table]
while cur:
blocks[table].append(cur)
cur = next[cur]
print(blocks[1:])
for table in range(Q):
frm, to, x = [int(x) for x in input().split()]
# print(frm, to, x)
p = prev[x]
if p > 0:
next[p] = 0
if top[to]:
prev[x] = top[to]
next[top[to]] = x
else:
# x is first block of TO
prev[x] = -to
bottom[to] = x
top[to] = top[frm]
top[frm] = p
else:
# x is last block
bottom[frm] = 0
if top[to]:
prev[x] = top[to]
next[top[to]] = x
else:
# x is first block of TO
bottom[to] = x
top[to] = top[frm]
prev[x] = -to
top[to] = top[frm]
top[frm] = 0
# print(prev)
# print(next)
# print(top)
# print(bottom)
# debugPrint()
# print()
pos = [0] * (N + 1)
for table in range(1, N + 1):
cur = bottom[table]
while cur:
pos[cur] = table
cur = next[cur]
for i in range(1, N + 1):
print(pos[i])他の人のコードを読むと、ここは双方向のリストにする必要はなく、机のトップと、箱の下の箱だけのリストでよいようだ
Related Pages
- →abc168×第三回 アルゴリズム実技検定×abc169×abc173×僕のatcoderの学び方(〜緑)×arc106×僕のatcoderの学び方(〜水色)×abc183×abc187×僕のatcoderの学び方(〜青)→
- →座標圧縮×setはメモリ食い×numba×numbaに複雑な型を渡す×numba_bisect×numpy.unique×長方形グラフ探索×番兵×numba_np.concatenate×csr_matrix×リンクトリスト×mprof×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]