ARC004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

問題

https://atcoder.jp/contests/arc004/tasks/arc004_2

<問題概要>

平面上に0～N番のN+1個の点がある。i番目の点とi+1番目の点の距離はd[i]である。0番目の点とN番目の点の距離の最大値と最小値を求めよ。

<問題読み替え>

N個の棒がある。これらをつなげた端と端の距離の最大値と最小値を求めよ。

<解法>

d[i]の総和をsum、d[i]の最大値をM1、２番目に大きい値をM2とする。

また、M1を抜いたd[i]の総和をsum'=sum-M1とする。

(1)最大値

まっすぐにのばせば最大になるのは明らかなので最大値はsum

(2)最小値

(ⅰ)M1>sum'の時

どう頑張っても最小値はM1-sum'=2*M1-sumより小さくならないので最小値は2*M1-sum

(ⅱ)M1<=sum'の時

端と端がくっついて最小値は0になりそうだがこれを証明する。

(端がくっつく条件はM1<=sum'であることを証明する)

まず、端がくっつく条件にd[i]の順番は関係ない。

なぜなら棒をベクトルとして考えると端がくっつくとはベクトルの総和が0であるということであり、このことは棒の順番を変えても成り立つからである。ここでM1の棒を抜いた棒の集合の端と端の距離の最大値と最小値を考える。この棒の集合を2グループに分けてそれらをつなげた棒Aと棒Bを作る。Aの長さをa,Bの長さをbとする。次の方法で分けることでabs(a-b)<=M2　①

とすることができる。

(分け方)

M1を抜いたd[i]をsortして、小さい順にA,Bに交互に振り分ける。

これでabs(a-b)<=M2となった。AとBのなす角をθとするとこれらの端と端の距離はD=(a^2+b^2-2*a*b*cosθ)^(1/2)

-1<=cosθ<=1より

abs(a-b)<=D<=a+bとなる。

Dは連続なのでabs(a-b)<=M1<=a+bを満たせばすべての棒を使ったときに端がくっつく。①と、M2<=M1よりabs(a-b)<=M1は常に満たしているので端がくっつく条件はM1<=a+b=sum'(証明終)

答え

最大値　sum

最小値　max(0,2*M1-sum)