CodeTON Round 1 : F. Parametric MST

意外にコードが短い。
https://codeforces.com/contest/1656/problem/F

問題

N点の完全グラフを考える。
各点iには整数A[i]が設定されている。

この時2点i,jを結ぶ辺のコストは、パラメータtを用いてW(i,j,t)=A[i]*A[j]+t*(A[i]+A[j])となる。

tが任意の値を取るとき、MSTのコストに上界があればそれを答えよ。

解法

Aを昇順にソートしておく。
B[i]=A[i]-tとすると、W(i,j,t)=B[i]*B[j]-t^2となる。

iを固定すると、MSTにおいてi番の点とつなぐ辺は0番か(N-1)番のいずれかとなる。
これを踏まえ、tをA[0]～A[N-1]まで動かしたときのコストと、tを極端に大きくまたは小さくしたときのコストを総当たりすればよい。

int T,N;
ll A[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
		}
		sort(A,A+N);
		
		if(A[N-1]*(N-2)+sum<0) {
			cout<<"INF"<<endl;
			continue;
		}
		if(A[0]*(N-2)+sum>0) {
			cout<<"INF"<<endl;
			continue;
		}
		ll s=A[N-1]*(N-2)+sum;
		ll v=-(N-1)*A[N-1]*A[N-1];
		ll ret=v;
		
		for(i=N-1;i>=1;i--) {
			v+=s*(A[i]-A[i-1]);
			ret=max(ret,v);
			s+=A[0]-A[N-1];
		}
		cout<<ret<<endl;
	}
}

まとめ

コードは短いけど考察はちょっとめんどい。