ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

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

・概要
平面上に N+1 個の点があり、それぞれ 0 から N までの番号が付けられています。
それぞれの点の位置はわかりませんが、0 以上 N 未満の整数 i について、i 番の点と i+1 番の点の距離 di はわかっています。
0 番の点と N 番の点の距離としてとりうる値の最大と最小を求めてください。


・解法
この問題はわりと解くのに悩みました・・・。

最大値は与えられる座標間の距離をすべて足すだけです。

最小値を求めるには、「三角形ができるか?」というのを考えていきます。
具体的には、0からNまでの座標から2点選んだとき、その選んだ2点と0とNをつないだ点の3つ頂点をもつ三角形を作ることができるかどうかを判定します。
そして三角形を作ることができるならば、最小値は0。
できないならば3辺の長さの差(辺の長い順にひいた絶対値)がその答えになります。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;

#define REP(i, x, n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i, n)    REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back

const int INF = (1<<29);
const double EPS = 1e-9;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};

int d[500];
int maxi, mini;

int main(){
   int n;
   cin >> n;
   rep(i,n)cin >> d[i];

   maxi = 0;
   mini = INF;

   //max
   rep(i,n)maxi += d[i];

   //min
   int sum[501];
   sum[0] = 0;
   REP(i,1,n+1)sum[i] = sum[i-1] + d[i-1];
   
   if(n==1)mini = maxi;
   else if(n==2)mini = abs(d[0]-d[1]);
   else{
      REP(j,0,n){
	 REP(k,j+1,n+1){
	    int a = sum[j];
	    int b = sum[k] - sum[j];
	    int c = sum[n] - sum[k];
	    //cout << a << "  " << b <<" " << c << endl;
	    if(a+c >= b && a+b >= c && b+c >= a)mini = 0;
	    else mini = min(mini, abs(abs(a-b)-c));
	 }
      }
   }
   
   cout << maxi << endl;
   cout << mini << endl;

   return 0;
}