考察
禁止組が最大10^5個しかないため、価格上位の組を高い順に調べれば、提供される組へ到達するまでに捨てる候補は高々L個である。全NM組を作るのでなく「次に高い組」だけを生成したい。
副菜を価格降順に並べると、主菜iを固定した組は a_i+b_1, a_i+b_2,… という降順列になる。求める候補列は、このN本の降順列のmergeとみなせる。
採用する候補: 各主菜の未調査先頭をmax-heapへ入れ、全組を価格降順に列挙する
棄却する候補: 全NM組の価格を列挙してsortする
N,Mはともに10^5であり、NM個の生成時点で時間・メモリ上限を超える。
棄却する候補: 最大価格から二分探索し、閾値以上の提供組があるか判定する
禁止組を除いた存在判定は構成できるが、各判定で価格順と禁止情報を突き合わせる必要があり、この問題では上位だけを直接列挙する方が単純で計算量も明確である。
副菜を価格降順にsortし、各主菜iについて先頭副菜との価格和・i・順位0をmax-heapへ入れる。最大候補をpopし、その元index対が禁止集合になければ価格和を答える。禁止なら同じ主菜の次順位をheapへ入れて続ける。
典型の発動条件
sorted listsのk-way merge
発動条件: 各グループ内の候補が単調順に並び、全体の上位だけが必要なとき。
主菜ごとの副菜価格列を降順列とし、各列の先頭だけをheapで競わせる。
禁止要素数による探索回数評価
発動条件: 候補を良い順に調べ、失敗する候補の総数が小さく制約されているとき。
提供されない組はL個だけなので、最初の有効候補は高々L+1回目に現れる。
問題固有の要素
価格行列a_i+b_jは各行を同じ副菜順で降順化できるため、一般の二次元最大探索をN本の列mergeへ落とせる。
別の問題へ持ち帰る視点: 和・積など片側の順序を固定しても単調性が保たれる二項候補では、全直積を作らず行ごとのfrontierだけを管理する。
正当性
heapから主菜iの現在候補を取り出した直後に、その主菜の次の副菜との組だけを追加すれば、未調査全体の最大値を失わない。 禁止判定には元の副菜indexが必要なので、降順sort後も価格と元indexを組で保持する。 heapには各降順列の最大未調査要素が必ずあり、禁止組をL個読み飛ばしてもL+1回以内に答えへ着くので、列挙数を禁止数に比例させられる。
実装上の注意
- 禁止集合はsort前の主菜・副菜indexで照合する。次順位がM未満のときだけpushし、価格和は64 bit整数で持つ。
復習の核
- 禁止組が0、各主菜の先頭候補が連続して禁止、最後の一組だけ有効な小ケースを全列挙と照合し、heap frontierの不変条件を確認する。
計算量と制約
時間
O(M log M+(N+L)log(N+L))、N主菜M副菜L禁止組。平衡木で禁止照合する場合はO(L log L)。
空間
O(N+M+L)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, M \leq 10^5; 0 \leq L \leq \min(10^5, NM - 1); 1 \leq a_i, b_i \leq 10^9; 1 \leq c_i \leq N; 1 \leq d_j \leq M; (c_i, d_i) \neq (c_j, d_j) if i \neq j.; All input values are integers.
出典