ARC 032 - 仕事計画

• 問題
• AC

辞書式順序の条件を無視すればただの区間スケジューリングなので、始点$a_i$でソートして逆から貪欲に選んでいけば仕事の数の最大数$k$が求まる。この際に得られた仕事の列が開始から

$$(a'_1, b'_1), (a'_2 b'_2), ..., (a'_k, b'_k)$$

となっているとする。このとき、次の性質があることに注目する:

• $k-1$個の仕事をこなすためには、少なくとも$a'_2$までには始めなければならないし、$a'_2$までに始めれば$k-1$個の仕事が可能である
• $k-2$個の仕事をこなすためには、少なくとも$a'_3$までには始めなければならないし、$a'_3$までに始めれば$k-2$個の仕事が可能である
• ...
• $1$個の仕事をこなすためには、少なくとも$a'_k$までには始めなければならないし、$a'_k$までに始めれば$1$個の仕事が可能である

これらの性質から、$k$個の仕事からなる辞書順最小のスケジュールを構成する方法が従う:

• $1$個目の仕事は$a'_2$までに終わるものならなんでも可能である。このうちインデックスが最小のものを$(l_1, r_1)$とする。
• $2$個目の仕事は$r_1$以降に始まって$a'_3$までに終わるものならなんでも可能である。このうちインデックスが最小のものを$(l_2, r_2)$とする。
• ...
• $k$個めの仕事は$r_{k-1}$以降に始まるものならなんでも可能である。このうちインデックスが最小のものを$(l_k, r_k)$とする。

こうして辞書順最小のスケジュール$(l_1, r_1), ..., (l_k, r_k)$が得られた……わけだが、実際にこのスケジュールを求める手順がまだ明らかでない。

時間$x$に始まって$y$に終わる仕事のインデックスを$f(x, y)$とするとき（複数ある場合、インデックスが最小のもの以外は捨ててよい）、仕事は二次元空間上の点とみなせるので、上の性質をさらに言い換えられる:

• $[0, a'_2] \times [0, a'_2]$上にある仕事について$f(x, y)$の最小値を求める。$(l_1, r_1)$で最小になるとする。
• $[r_1, a'_3] \times [r_1, a'_3]$上にある仕事について$f(x, y)$の最小値を求める。$(l_2, r_2)$で最小になるとする。
• ...
• $[r_{k-1}, +\infty] \times [r_{k-1}, +\infty]$上にある仕事について$f(x, y)$の最小値を求める。$(l_k, r_k)$で最小になるとする。

ここまで整理すると、$\min$を乗せたrange treeで実行できる手順になっている。計算量は${O}(N \log^2 N)$。

---

線形で求まるのは、手順を示されれば確かにとなるけどまったくわからなかった。

今出題されたら、もう少し制約が大きくなって$\log^2$は落ちる気がする。この方針のままでも、2D range tree + fractional cascading + 構築${O}(N)$クエリ${O}(1)$のRMQで$\log$を1つにできそう？ でも、そもそも平面走査的になんとかできないのかな。