NISHIO Hirokazu[日本語][English]

ABC170 E

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)の対を入れてるのに対してこちらはレートだけを入れてるのが独特
    • 最大値はセグメント木に入れる

  • https://atcoder.jp/contests/abc170/submissions/14360320

    • レートに対して座標圧縮を掛ける、なぜ？
    • 集合はheapqで表現
    • 最大値の集合はBinary Indexed Tree(フェニック木)
      • 更新が効率的に行える
      • 座標圧縮は木のサイズを小さくするのに寄与する

これを踏まえて

(C)NISHIO Hirokazu / Converted from Markdown (ja)
Source: [GitHub] / [Scrapbox]