AtCoder Regular Contest 4 B. 2点間距離の最大と最小 ( Maximum and Minimum )
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の21日目のエントリです．
ARCのB問題埋め．
問題概要
- 点iと点i+1の距離，di与えられる (i=0~N-1)
- 点0と点Nの距離として考えられる最大値，最小値を求める
解法
- 最大値は点が一直線に並んだ場合，すなわちdiの和
- 最小値は
- 三角形が作れる時は0
- 作れない時はできるだけ三角形に近づけて一番長い辺から残りの2辺を引いたもの
- 最大値の場合の一直線に並んだ線を2カ所で折り曲げると考え，その2カ所を探索する
- 2カ所を決めたら辺の長さを求める
- その際愚直に求めるとTLEとなるので，累積和を使って求める
