PAST5E
素朴に全探索すれば良い
はみださないように全探索するために、スタンプでない側にスタンプの幅分の番兵をつけた
番兵をつけるコード自体は既に書いてあった
今まで、一度に二つ読むことはなかったのでグローバル空間に番兵つきの幅を書き込んでいた
今回は二つ読むのでその値を参照しないで再計算するコードになった
改善の余地はあるが、使う頻度低そう…
回転は想定してなかったので今回新たに書いた
回転時に縦横の長さが交換される
スタンプの側だけを交換するべきだが取り違えててWAした
pythondef solve(H, W, world, stamp):
S = max(H, W)
# world
WW = W + 2 * S
WH = H + 2 * S
# stamp
SW = W
SH = H
def conflict():
for x in range(SW):
for y in range(SH):
if stamp[y * SW + x] == 0:
if world[(sy + y) * WW + (sx + x)] == 0:
# conflict
return True
for _rot in range(4):
for sx in range(S + W):
for sy in range(S + H):
if conflict():
continue
return True
# rotate
new_stamp = [0] * (W * H)
for x in range(SH):
for y in range(SW):
new_stamp[y * SH + x] = stamp[(SH - 1 - x) * SW + y]
stamp = new_stamp
SW, SH = SH, SW
return False公式解説
スタンプの側を座標の列で持てば回転の実装も素直に書ける、なるほど
Related Pages
- →地図読み込み時に番兵をつける×数列を有理式にする×ラグランジュ補間×対称性で次元削減×余事象を引く×未ac×足し算の順序を変える×xごとのf(x,y)の和はyごとのf(x,y)の和×最大値の期待値×順位統計量×maxの不等号は不等号のand×0,1→
- →座標圧縮×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]