https://yukicoder.me/problems/no/909
求める最大距離はd=min1≤i≤N(Xi+Yi)です。
これ以上大きなdNG>min1≤i≤N(Xi+Yi)にはできません。
なぜなら、たぴ0とたぴN+1をdNG離して配置すると、例えばmin1≤i≤N(Xi+Yi)をみたすたぴiminをどのように配置しても、たぴ0からXiminより大きく離れるか、たぴN+1からYiminより大きく離れるからです。
一方、d=min1≤i≤N(Xi+Yi)は以下の構成で達成できます。
たぴ0を0に配置します。
たぴN+1をdに配置します。
たぴi(1≤i≤N)について、
-
d≤Xiのときdに配置します。こうすればたぴ0からXi以下であり、たぴN+1からの距離は0なのでYiも自然と満たされます。
-
d>Xiのとき、Xiに配置します。このとき、たぴN+1からYi以下という条件もみたしています。なぜなら、Xi+Yi≥dより、Yi≥d−Xiだからです。
https://yukicoder.me/submissions/397044