ABC370 D Cross Explosion の解法と自作回答

ABC370 D の復習をしていたのだけど、解説では二分探索を使って破壊した壁の管理を行えばよいとなっていた。
二分探索なら前回の記事(C# で lower_boundをListの拡張関数として実現する)で書いた、Listを拡張したLowerBoundですぐ見つかる！と意気込んで回答した。
結果はTLEがぼこぼこ出る。再帰で書いた初回の回答と変わらん処理速度。

なんでなんだ。。。

原因の発見

これ、落ち着いてみたらわかるんだけど、探索した後に削除するんだよね。
LowerBoundでindexはわかっているから、List.RemoveAtすればO(1)だろ！と思ってたら、List.RemoveAtは、計算量O(N)。
内部的には該当要素を削除した後、後続の値を詰める処理が発生するとのこと。
先頭に近ければ近いほど前に詰める処理が発生するそうでした。

そりゃ再帰で消す場所探すのと変わんないのよ。

List.BinarySearchの適用できる場所

挿入も削除と同じでList.InsertはO(N)になるので、削除と同じ。
つまり、BinarySearchは検索だけで挿入や削除を伴う場合はListを使い続ける限り改善しない。
前回のABC371 Dは検索だけでよかったからAC出せたということでした。

結論

標準コレクションや関数は中身ちゃんと把握してから使おうね。
（それはそう。）