公式解説に倣い、

• \((u_i, v_i)=(T_i+X_i, T_i-X_i)\)
• \(\{i\}\leq\{j\}\Leftrightarrow(u_i\leq u_j)\land(v_i\leq v_j)\)

で定義したとき、答えはリンゴの全体集合を分割するために必要な鎖の個数の最小値です。

鎖の個数が最小であるような鎖分解 \(D\) は、以下の貪欲法によって構成できます。

\(D\) を \(\text{\O}\) で初期化する。まだ回収していないリンゴがある限り、以下の操作を繰り返す。

1. 鎖 \(C\) を \(\text{\O}\) で初期化する。
2. リンゴロボを \(1\) 台追加し、座標 \((u^\prime, v^\prime)\) を \((-\infty, -\infty)\) で初期化する。
3. まだ回収していないリンゴのうち、「座標が \((u_i, v_i)\) であって、\(u^\prime\leq u_i\) かつ \(v^\prime\leq v_i\)」を満たすリンゴが存在する限り、以下の操作を行う。
   • 上記の条件を満たすもののうち、\((u_i, v_i)\) が辞書順最小である \(\{i\}\) を選ぶ。
   • 座標 \((u^\prime, v^\prime)\) を \((u_i, v_i)\) に更新し、リンゴ \(i\) を回収する。
   • \(C\) に \(\{i\}\) を追加する。
4. \(D\) に \(C\) を追加する。

実装する際、セグメント木や平衡探索木などを用いれば、条件を満たすリンゴを高速に求めることができ、\(M=\max\{T_i+X_i\}\) として計算量 \(O(M+N\log(MN))\) または \(O(N\log N)\) の解法が得られます。

実装例 (C++)

貪欲法の正当性を証明します。Dilworth の定理より、鎖分解に含まれる鎖の最小の個数は任意の反鎖の大きさの最大値です。よって、\(D\) の大きさと反鎖の最大の大きさが一致することを示せばよいです。

貪欲法において最初に追加されたリンゴロボについて、回収したリンゴの集合を \(B\) とします。貪欲法の定義より、\(B\) は非空な鎖です。

\(B\) に属するリンゴの座標を辞書順に並べた列を \(((u^B_1, v^B_1), (u^B_2, v^B_2), \dots, (u^B_{|B|}, v^B_{|B|}))\) とします。

全体集合における大きさが最大であるような反鎖 \(A\) について、\(|B\cap A|=1\) が常に成立することを示します。

\(B\) に含まれるどの \(2\) つのリンゴも比較可能であり、\(A\) に含まれるどの \(2\) つのリンゴも比較不能であるため、\(|B\cap A|\leq1\) です。

\(B\cap A=\text{\O}\) と仮定します。\(A\) に属するリンゴの座標を辞書順に並べた列を \(((u^A_1, v^A_1), (u^A_2, v^A_2), \dots, (u^A_{|A|}, v^A_{|A|}))\) とします。リンゴの比較の性質により、\(u^A_1\lt u^A_2\lt\dots\lt u^A_{|A|}\) かつ \(v^A_1\gt v^A_2\gt\dots\gt v^A_{|A|}\) です。

• \((u^A_1, v^A_1)\) が \((u^B_1, v^B_1)\) より辞書順で小さいと仮定すると、貪欲法の手順3より \((u^A_1, v^A_1)\) にあるリンゴは \((u^B_1, v^B_1)\) にあるリンゴよりも先に回収される。これは \(B\cap A=\text{\O}\) に矛盾するため、\((u^A_1, v^A_1)\) は \((u^B_1, v^B_1)\) より辞書順で大きい。
• \((u^A_1, v^A_1)\) が \((u^B_{|B|}, v^B_{|B|})\) より辞書順で大きい場合を考える。このとき、\(v^B_{|B|}\leq v^A_1\) と仮定する。貪欲法の手順3より \((u^B_{|B|}, v^B_{|B|})\) にあるリンゴを回収した直後に \((u^A_1, v^A_1)\) にあるリンゴは回収される条件を満たし、\(B\cap A=\text{\O}\) に矛盾する。したがって \(v^B_{|B|}\gt v^A_1\) であり、辞書順を考慮すると \(u^B_{|B|}\lt u^A_1\) である。
  • しかしながら \(u^B_{|B|}\lt u^A_1\lt\dots\lt u^A_{|A|}\) かつ \(v^B_{|B|}\gt v^A_1\gt\dots\gt v^A_{|A|}\) が成立するため、\((u^B_{|B|}, v^B_{|B|})\) にあるリンゴは \(A\) に属するどのリンゴとも比較不能である。そのリンゴを \(A\) に追加することによって得られる集合 \(A^\prime\) は反鎖であり、\(|A^\prime|=|A|+1\) となる。これは \(A\) が大きさ最大の反鎖という前提に矛盾するため、\((u^A_1, v^A_1)\) が \((u^B_{|B|}, u^B_{|B|})\) より辞書順で大きい場合は不可能である。
• 上記の場合はいずれも仮定に矛盾するため、「座標 \((u^A_1, v^A_1)\) は \((u^B_j, v^B_j)\) より辞書順で大きく、さらに \((u^B_{j+1}, v^B_{j+1})\) より辞書順で小さい」という条件を満たす \(j\) が存在する。このとき、\(v^B_j\leq v^A_1\) と仮定する。貪欲法の手順3より、\((u^B_j, v^B_j)\) にあるリンゴを回収した直後に \((u^A_1, v^A_1)\) にあるリンゴは \((u^B_{j+1}, v^B_{j+1})\) にあるリンゴの代わりに回収され、\(B\cap A=\text{\O}\) に矛盾する。したがって \(v^B_j\gt v^A_1\) であり、辞書順を考慮すると \(u^B_j\lt u^A_1\) である。
  • 先述と同様な議論より、\((u^B_j, v^B_j)\) にあるリンゴを \(A\) に追加することによって得られる集合は反鎖であり、前提に矛盾する。よってこの場合も不可能である。

いずれの場合も不可能であるため、\(B\cap A\neq\text{\O}\) です。したがって、\(|B\cap A|=1\) となります。

\(B\) に属するリンゴを全体集合から削除した後の問題を考えます。削除後、\(A\setminus(B\cap A)\) は大きさ最大の半鎖であり、その大きさは \(|A|-1\) です。よって、\(B\) を回収した後に必要なリンゴロボは \(1\) 台減ります。\(2\) 台目以降のリンゴロボについても同様な議論が成り立つため、貪欲法で使用するリンゴロボの台数は \(|A|\) と一致します。

以上より、前述の貪欲法は正当です。