yukicoder No.909 たぴの配置(★2)
解答:#472634 (C++14) No.909 たぴの配置 - yukicoder
解答:mn = min(xi + yi)とすると、0番めのたぴは座標0、N+2番目のたぴは座標mnに置くことができる。
このとき、i番目のたぴはmax(mn - yi, 0)に置くとよい。これはi番目のたぴの座標条件を満たす。下記にて証明する。
0番目のたぴからの距離は、max(mn - yi, 0)である。mn - yi = 0の時は問題ないので、mi-yiが、mnの最小性よりmn - yi - xi ≦ 0であり、mn - yi ≦ xiが成り立つ。
N+2番目のたぴからの距離は、mn - max(mn - yi, 0)である。mn - yi > 0 の場合、これはmn - mn + yiyiとなり問題ない。mn - yi = 0の場合、mnとなるが、これはmn = yiよりyiであり、これも問題ない。