8VC Venture Cup 2016 - Elimination Round : E. Simple Skewness

考察不十分だった。
http://codeforces.com/contest/626/problem/E

問題

N個の整数からなる集合が与えられる。
これらのうち、任意個数を抜き出した部分集合を考える。
抜き出した集合の(平均値-中央値)が最大となるような部分集合を答えよ。

解法

偶数個抜き出すケースは、同着最大はあっても単独最大にはなり得ない。
中央値の２値が異なる場合、大きい方を集合から外した方が、平均値の下がり幅より中央値の下がり幅が大きくなるためである。

まず最初に集合全体を昇順ソートし、その数列をAとしよう。
それぞれ中央値がA[x]の場合、平均値をどこまで大きくできるかを考える。
全体の要素数が2k+1個だとすると、x番目以降の要素からk個、x番目より前の要素からk個を抽出することになる。
平均値を大きくしたいのだから、当然2k+1個の取り方はA[x]を中央値とするためにA[(x-k)...x]、A[(N-k)...(N-1)]となる。

xを固定したとき、この部分列の平均値はkに対して上に凸になる(kを大きくするほど、Aの部分列に含まれる数値が小さくなるため、平均値の増加率が減少する)。
よって平均値を最大化するkは三分探索で求められる。
計算途中の平均値を小数で保持すると精度差で失敗するので、有理数の形で持とう。

まとめると、各A[x]を中央値とするケースを総当たりし、(2k+1)要素の平均が最大となるkを三分探索で求めていきながら、平均値-中央値の最大値を求めていけば良い。

int N;
int 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 bp=0,br=1;
	int M=0,num=0;
	
	for(i=1;i<N-1;i++) {
		int L=0,R=i;
		while(L+3<R) {
			int M1=(L*2+R)/3;
			int M2=(L+R*2)/3;
			ll m1p=S[i+1]-S[i-M1]+S[N]-S[N-M1]-1LL*A[i]*(2*M1+1);
			ll m2p=S[i+1]-S[i-M2]+S[N]-S[N-M2]-1LL*A[i]*(2*M2+1);
			if(m1p*(2*M2+1)>m2p*(2*M1+1)) R=M2;
			else L=M1;
		}
		
		for(x=L;x<=R;x++) {
			ll tp=S[i+1]-S[i-x]+S[N]-S[N-x]-1LL*A[i]*(2*x+1);
			ll tr=2*x+1;
			if(tp*br>bp*tr) bp=tp, br=tr, M=i, num=x;
		}
		
	}
	
	cout<<(1+num*2)<<endl;
	for(i=M-num;i<=M;i++) cout<<A[i]<<" ";
	FOR(i,num) cout<<A[N-num+i]<<" ";
	cout<<endl;
	
}

まとめ

kを二分探索・三分探索する解法は本番思いついたのに、平均値が上に凸になる事に自信が持てずその解法を取れなかった。
どうせ残り時間少ないなら突っ走るのもありだったな。