#問題

No.909 たぴの配置 - yukicoder

競技プログラミングの練習サイト

yukicoder.me

#考察

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

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

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

たぴ$0$を$0$に配置します。 たぴ$N+1$を$d$に配置します。

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

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

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

#397044 (Ruby) No.909 たぴの配置 - yukicoder

競技プログラミングの練習サイト

yukicoder.me