Alien’s Trick (あるいはラグランジュ緩和) を考えると，一回の食事会にコスト \(c\) がかかるときに profit がいくつになるか，が \(1\leq c \leq M\) すべてについて求まっていれば良い．

\(c\) を固定したときの問題を考える． 実はLPで定式化できる(※)ので双対を取ると以下のような問題になる．

• 区間 \([L_i,R_i]\) をいくつか選ぶ． \(c+1\) 個以上重なる部分があると不適． 最大何個取れるか？

正確には，\(M\) から上の問題の答えを引いた値が \(c\) に対応する profit だが，同じことなので以降は上の形で解く．

\(c=1\) は有名問題で，以下のような貪欲で解ける．

• カーソルを \(0\) に置く．その後次の操作を繰り返す．

• 区間であって，以下の条件を満たすものをとり，カーソルをその区間の右端にセットする．

  • 左端がカーソルより右にある
  • その中で右端が最小

• 区間が取れなくなったら終わり．

実は \(c>1\) でも同じように解ける． 今 \(c=x\) の解が求まっているとする． \(c=x+1\) の解は，上とほぼ同じ貪欲を今まだ使っていない区間に対して走らせれば出てくる． “ほぼ”同じなので違う部分がある． カーソルを区間の右端にセットしたあと，そこから左に戻すことができる． 戻せる条件は，今までに使った区間がどれだけ重なっているかを見て，\(c\) 個未満である限り戻って良い，というものである．

上の貪欲の正当性は，上記の問題をフローで解いたときにその動きがどうなるか考えるとわかる．

遅延評価 Segment Tree 上の二分探索等を用いることで，この貪欲は \(O(M \log M)\) 時間で実行可能である．

計算量は全体で \(O(N+M \log M)\) になる． \(O(M\sqrt{M}\log(M))\) 解法と区別するため，TL は少し厳し目に設定されている．そのため，\(O(M \log^2M)\) 解法では定数倍が速くないと AC できないことがある．

実装例

※LP での定式化について

最小化問題を作る． 変数 \(x_0,x_1,\cdots,x_N\) を用意する． \(x_i-x_{i-1}\) を \(i\) 日目に食事会を開く回数と対応させる． つまり，\(x_{i-1} \leq x_i\) という制約と，\(K(x_N-x_0)\) というコスト関数を作る．

各 \((L_i,R_i)\) に対しては，まず変数 \(d_i\) を導入し，区間 \([L_i,R_i]\) 内に食事会があるか否かと対応させる．制約 \(0 \leq d_i \leq 1, d_i \leq x_{R_i}-x_{L_i-1}\) とコスト関数 \(1-d_i\) を追加すればよい．

この LP が整数解を持つことは，totally unimodular 性から証明できる．また，双対問題を経由して証明することもできる．この部分の詳細は省略する．

この LP の双対問題を考えると，mincostflow とほぼ同じ形になる．これを更に整理すると，上述の問題に帰着される．