kmjp's blog

競技プログラミング参加記です

Codeforces #1060 : Div2. E. No Mind To Think

タイトル名と問題内容の関係がよくわからなかった。
https://codeforces.com/contest/2154/problem/E

問題

N要素の整数列Aが与えられる。
以下の処理を最大K回まで行える時、Aの総和を最大化せよ。

Aのうちx(=奇数)個の要素を選び、それらをそのmedianに置き換える。

解法

Aを昇順に置いていたとする。
medianがA[i]となるようにする場合、m回目の処理ではA[(m-1)*(x/2)]...A[m*(x/2)-1]及びA[i]...A[i+(x/2)]を選ぶのが良い。
median A[i]を総当たりしながら、K回処理したときに上記置き換えによる結果が最大となるmを二分探索しよう。

int T,N,K;
int A[202020];
ll S[202020];

ll hoge(int i,int l) {
	return S[N]-(S[i+l+1]-S[i+1])-S[l*K]+1LL*(K+1)*l*A[i];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		sort(A,A+N);
		FOR(i,N) S[i+1]=S[i]+A[i];
		ll ret=S[N];
		FOR(i,N) {
			int R=(i+K-1)/K;
			if(i+R<N) {
				ret=max(ret,1LL*(i+1+R)*A[i]+S[N]-S[i+1+R]);
			}
		}
		
		FOR(i,N) {
			int ma=min(i/K,(N-1-i));
			if(ma<=100) {
				for(l=1;l<=ma;l++) ret=max(ret,hoge(i,l));
			}
			else {
				int L=0,R=ma;
				while(R-L>=5) {
					int M1=(L*2+R)/3;
					int M2=(L+R*2)/3;
					ll v1=hoge(i,M1);
					ll v2=hoge(i,M2);
					ret=max({ret,v1,v2});
					if(v1>=v2) R=M2;
					if(v2>=v1) L=M1;
					
				}
				for(l=L;l<=R;l++) ret=max(ret,hoge(i,l));
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

手間取ったけどコードはDより短いんだな。