yukicoder No.909 たぴの配置 (★2)

#問題

https://yukicoder.me/problems/no/909

#考察

求める最大距離はd=min1iN(Xi+Yi)d = \min_{1 \leq i \leq N}(X_i + Y_i)です。

これ以上大きなdNG>min1iN(Xi+Yi)d_{NG} > \min_{1 \leq i \leq N}(X_i + Y_i)にはできません。 なぜなら、たぴ00とたぴN+1N+1dNGd_{NG}離して配置すると、例えばmin1iN(Xi+Yi)\min_{1 \leq i \leq N}(X_i + Y_i)をみたすたぴimini_{min}をどのように配置しても、たぴ00からXiminX_{i_{min}}より大きく離れるか、たぴN+1N+1からYiminY_{i_{min}}より大きく離れるからです。

一方、d=min1iN(Xi+Yi)d = \min_{1 \leq i \leq N}(X_i + Y_i)は以下の構成で達成できます。

たぴ0000に配置します。 たぴN+1N+1ddに配置します。

たぴi(1iN)i (1 \leq i \leq N)について、

  • dXid \leq X_iのときddに配置します。こうすればたぴ00からXiX_i以下であり、たぴN+1N+1からの距離は00なのでYiY_iも自然と満たされます。

  • d>Xid > X_iのとき、XiX_iに配置します。このとき、たぴN+1N+1からYiY_i以下という条件もみたしています。なぜなら、Xi+YidX_i + Y_i \geq dより、YidXiY_i \geq d - X_iだからです。

https://yukicoder.me/submissions/397044