https://twitter.com/kinaba のログ (twilog の方が便利です。)
| #srm #topcoder さっきから頭の中がうっさうさ状態で困っているので道連れを増やす試み http://topcoder.g.hatena.ne.jp/cafelier/20100706/1278459172 | |
| え、流れ読めてないけどマルチインデックスのランダムアクセスの削除は普通に線形時間かかるような。。。 | |
| 帰宅＆流れ追った。@tanakh @cpp_akira @kikairoya multi_index<set,vector>的な奴は、キーアクセスO(log n)添字O(1)キー挿入(添字側は末尾挿入)O(log n)キー削除O(n)なので高速削除が要るなら要件に合わぬと思われ。 | |
| 添字アクセスの方の並び順が重要でなくて、単に乱数で１個 O(1) で取り出せるだけでよければ、random_accessのremoveの実装を１，２行いじって削除時は末尾要素を持ってきて埋める実装に変えればキー削除O(log n)なのが作れると思いますけども | |
| http://d.hatena.ne.jp/kusano_prog/20100705/1278361318 ICPCのE問題DPで解いたよという解を見ている。これも簡潔だなあ。E1のジャッジデータのネタはわかりにくい…とかそれ以前にスペルミスってる気がする |