Typical DP Contest K - ターゲット

問題
提出コード

解法

区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。
まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標とがわかっているとき、円と軸が接する2点は、とになります。
すると、このからを、一つの区間としてみることができます。番目の円に対するを、をとします。
あるサイズのターゲットが存在するとき、もう一つサイズを増やすには、
今あるターゲットの中で最大の円と、新しく加わる円が次のような関係になっている必要があります。
かつ
図で表すとこのような状態です。
さて、ここで区間スケジューリングのように、区間の終わり、つまり側に注目すると、を降順でソートすることで、円をいくつか選び、その円でサイズのターゲットが作成できたとき、個を大きさ順に並べると、上のソートした順番と同じになります。
ので、について降順でソートしておけば、あとはについてのみ考慮すれば、前から順番に円を選んでいくだけでターゲットが作成できるということです。
としたいのですが、コーナーケースが存在します。となるようなケースになります。このような場合は、について昇順になっていると、とのみでターゲットのサイズを増やせるかどうかの判定ができないので、降順にならべておけばよいです。

ここで、LISを思い出すことができれば、
サイズのターゲットを作成できるとき、その中で最小の円についてのの最小値
とすると、この問題を解くことができます。
円を合わせてサイズのターゲットを作成するときに必要な条件が、であるので、はできるだけ小さくしておきたいからです。
の中の要素は昇順に並んでいますので、について見ているとき、のlower_boundを探しその部分を更新していき、なければ今最大のに1追加した場所、つまりにを格納する、という操作を行えばよいです。これを回繰り返すと、値が格納されているのうち最大の値が答えになります。