ABC184E
from ABC184
距離を1ずつ増やしながら幅優先探索
必要な値を使いやすい形で読み込むところが泥臭い
スタートとゴールは地図に書かずに別途渡して欲しかった
地図を1次元配列に入れるライブラリをゴリゴリ書き換えることになった
そこは特に面白いことはない
幅優先探索でTLEしたのでワープの部分が良くないと思いこんでジタバタして4回もTLEしてしまった
同一文字のワープは1回しか使わないことは把握してて、2回試そうとしないように工夫してたのだが、その工夫が足りないのかと思ってしまった
結局原因はそこではなく「次に訪問する頂点」をリストで持ってるところだった
集合に変えたらAC
AtCoder失敗リストに書いとこう
pythondef solve(data):
to_visit = [START]
DIR4 = dir4()
ret = 0
while to_visit:
new_visit = []
for p in to_visit:
if p == GOAL:
return ret
v = data[p]
data[p] = -1
if v > 0: # WARP
for p2 in WARP[v]:
data[p2] = 0
new_visit.append(p2)
WARP[v] = []
for d in DIR4:
p2 = p + d
if data[p2] >= 0:
new_visit.append(p2)
to_visit = set(new_visit)
ret += 1
return -1Related Pages
- →atcoderエントリーポイント×AtCoder失敗リスト×二分探索チェックリスト×列に対して決まる値→列の区間でdp×最大化を二分探索で×実数に対する大小判定×値域と定義域の交換×最小カットに帰着×競技プログラミングで解法を思いつくための典型的な考え方×問題変換→
- →僕のatcoderの学び方(〜青)×past5o×AtCoder失敗リスト×abc175e×abc174f×abc172e×abc178f×arc106c×arc106×arc105c×arc105d×arc104c×arc107d×貪欲法×最小カットに帰着→
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜PAST上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×AtCoder失敗リスト×AtCoderEntrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
"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]