脳log[20210809]

2021年08月09日 (月) [AtCoder] 昨日の ABC213。前回が３完だったので今回は E 問題まで解けて良かったんだけど、E 問題を提出したのがコンテスト終了から６分後だったのだよね>提出 #24891967。１発 AC なのが余計に悔しい無念の４完。■どこかの週記で E 問題が 01BFS だと読んだ。名前だけは知っている！「01-BFSのちょっと丁寧な解説 - ARMERIA」実装の練習をして次は時間内に……。幅優先探索とダイクストラ法の中間みたいな位置づけなのか。両端キューの先頭から処理を開始して先頭なり末尾なりに要素を追加するっていうけど、そのあと処理をどう継続するのかがよくわからなくて実装が見えないんだよね(だから名前だけを知っている状態)。えっと、デックをイテレートしようとするからわからなくなるのであって、空になるまで shift を繰り返すみたい。■例題に挙げられている「器物損壊！高橋くん」は先月解いていた>提出 #24378783。しかしこれも 1.8 KB 書いていてかなり時間をかけたはず。たしか連結成分を列挙してから２回、塀を壊しての連結成分のマージを行った。結局 01BFS って、固有の実装テクニックがなくてもなんとかなるのでは？ だけど早く書きたいねえ。