ABC170 問題E Smart Infants 20万個の数値が20万個の集合を20万回動き回る。 このとき「集合の最大値」の最小値を各移動ごとに求めよ、という問題。
コンテスト中の思考 当然、各移動ごとに各集合に対してO(N)の処理をしたらTLEするだろう。 最小値をサッと取り出したいわけだからheapq ヒープキュー 優先度付きキュー - Wikipedia かな？
しかし数の移動に伴って、「最大値の集合」から最小値以外の値が取り除かれることがある。例: {1}, {2}, {3} → {1}, {2, 3}, {} うーん、ソート済みの配列に対する二分探索で目的のものを見つけて…いや配列への追加削除がO(N)だから追加削除を繰り返す攻撃でTLEにされるな。
リンクトリストにすることで追加削除のコストを下げる…いや、それだと削除対象を見つけるのがO(N)じゃん…じゃあ双方向リストにして、かつ各オブジェクトへのインデックスをつける？？？？
解答考察編。multiset - C++ Reference 平衡二分探索木 - Wikipedia などの意見が…なるほど追加削除O(N)をO(1)にしようとして「あちらを立てればこちらが立たず」だったが、全般的にO(logN)にすれば良いのか。方向性はわかった。
それで具体的な実装はどうするのかな…あれ？heapqを使ってる人がいるぞ？ https://atcoder.jp/contests/abc170/submissions/14361676 なるほど。ヒープキューの先頭以外の要素を取り除くコストは高いが、取り除かなければ良い、その代わり読み飛ばす仕組みをつければ良い、と。
- 集合から離れた人は先頭以外の場合は取り除かない
- 先頭の人が取り除かれた場合の次の人を探すタイミングで「同じ人」と「現時点で他の集合に入ってる人」を取り除く
- 「集合ごとの最大スコアのヒープキュー」も更新時に古い要素を取り除かない
- 代わりに各集合ごとに「自分が最後に最大スコアを更新した時刻」を記録する
- 出力のために先頭要素を取得した時点で、それが古いデータであれば捨てる
というわけで参考にしつつ書いたコードはACになった https://atcoder.jp/contests/abc170/submissions/14371172
感想
- これでTLEしないということに確信が持てない…
適当なAVL木の実装を持ってきて置き換えてみた →コードはシンプルになるが、TLE オーダーはO(logN)のはずだが定数倍が大きい？
PyPy実装の人の速い方から5件をみる
-
個別の集合を持つのには4人がheapq。数が多いのでツリー構築はオーバーヘッドが大きいから避けられてるのだろう。削除をする代わりに読み飛ばすアプローチは広く使われてるようだ。一人だけset、つまりハッシュマップ的アプローチでやってる人がいた。意外な抜け道。
-
最大値の集合を持つのには、セグメント木3人、heapq1人、フェニック木1人。フェニック木も面白そうだけど、とりあえずセグメント木が使えるようになりたいなーという気持ちになった。
-
https://atcoder.jp/contests/abc170/submissions/14369529
- 二つのheapqで集合に入った数値と抜けた数値を保管
- セグメント木で最小値を求める
-
https://atcoder.jp/contests/abc170/submissions/14332420
- シフトを使ってるのはタプルを使わずに数値をパックするため
- heapqに入れる、離れた人を先頭取得時に取り除く
- 最大値の集合もheapqに入れる
- 最小値の人が、最小値の人の所属する集合の最大値でないなら読み飛ばす
- それでいいのか？？
-
https://atcoder.jp/contests/abc170/submissions/14338427
- heapqに入れる、離れた人を先頭取得時に取り除く
- 移動元と移動先の最大値をセグメント木に入れる
- この人のセグメント木のコードは読みやすい
-
https://atcoder.jp/contests/abc170/submissions/14349092
- 集合を集合(set)で表現
- 集合の最大値は普通にmaxで計算
- それでTLEならないのか？
- 単純に真似したら一つの集合に密集してるhandmade06などのテストケースでTLEになった
- よく読むとうまい工夫があるのかもしれない
- 他のheapqアプローチが(レート, 人ID)の対を入れてるのに対してこちらはレートだけを入れてるのが独特
- それでTLEならないのか？
- 最大値はセグメント木に入れる
これを踏まえて