競技プログラミング用 知識集積所
ABC457G - Catch All Apples
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
時刻T1に位置X1におちてくるリンゴと時刻T2に位置X2におちてくるリンゴ、これらを同じロボが回収できる条件は、T1<=T2の場合、
|X1-X2| <= T2-T1
つまり
T1+X1 <= T2+X2 かつ T1-X1 <= T2-X2
である。つまりは逆に、T+XとT-Xの片方が増加して片方が減少していると別ロボが必要になる。
X+TとX-Tの両方が増加していると、という言い方もできる。
X+TとX-Tの両方が増加していると、という言い方もできる。
ということは、全リンゴのデータをX+Tの昇順に並べて、X-Tの（狭義の）最長増加部分列を探せば、その長さが答え。
X+Tが重複したときにそのうち1つしか採用できない点は、タイブレークでX-T降順にしておくことで自動的に解決される。
X+Tが重複したときにそのうち1つしか採用できない点は、タイブレークでX-T降順にしておくことで自動的に解決される。
