yukicoder : No.972 選び方のスコア

最初★2.5か～と思って取り組んだら意外に手間取った。
https://yukicoder.me/problems/no/972

問題

N要素の整数列A[i]が与えられる。
ここから任意の部分列を考える。
部分列における(各要素-中央値)を最大化せよ。

解法

Aを昇順にしておく。
中央値を考える際、偶数長を取るメリットはないので、奇数長とすることを考える。
中央値となる要素A[m]を総当たりして考えよう。

K=2p+1とすると、A[0..(m-1)]からp個、A[(m+1)...(N-1)]からp個とることになる。
当然Aが昇順なので大きい順にとるのがよい。
この際、pを1増やすことで得られる部分列の総和の増分が2*A[m]より大きい間はpを増やすメリットがある。
よって、pの最良の値は二分探索で得ることができる。

int N;
ll A[202020];
ll S[202020];

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

まとめ

最初、頭からいくつかと後ろからいくつかとる誤解法を取ってしまった。