コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
供養
解法
- 各セットの最小値の集合 $A$ と、$A$ の各要素 $a_{i}$ を最小値とするセットの最大値 $b_{a_{i}}$ の集合 $B$ を持っておく
- $A$ から、$s_{j}$ 以下で最大の $a_{l}$ と、$s_{j}$ 以上で最小の $a_{r}$ を見つける
- このとき、選択される問題は $\min(b_{a_{l}}, s_{j})$ と $a_{r}$ のうち $s_{j}$ に近いほうである
- これによって選択される問題を $p_{j}$、$p_{j}$ が所属していた問題セットの最小値を $a_{i}$ とする
- $p_{j}, a_{i}$ の値で $A, B$ を以下のように更新する
- $p_{j} = b_{a_{i}}$ ならば $b_{a_{i}} = b_{a_{i}} - 1$ とし、その結果 $a_{i} \gt b_{a_{i}}$ となるならば $a_{i}$ を$A$ から除外する
- $p_{j} \lt b_{a_{i}}$ ならば以下の操作を実施する
- $p_{j} + 1$ を $A$ に追加し、$b_{p_{j} + 1} = b_{a_{i}}$ とする
- $p_{j} = a_{i}$ ならば $a_{i}$ を $A$ から除外する
- $p_{j} \gt a_{i}$ ならば $b_{a_{i}} = p_{j} - 1$ とする
- $A$ をAVL木で持てば探索・追加・削除がすべて1回あたり $O(\log (N + M))$ で可能になる
- 全ての操作が終わったら $p_{j}$ を出力する
計算量はテストケースあたり $O( (N + M) \log (N + M) )$
公式解説
躓いた点
