yukicoder : No.2627 Unnatural Pitch

やっぱり★4になったか。
https://yukicoder.me/problems/no/2627

問題

N要素の整数列Aと正整数Kが与えられる。

• Aの全要素をインクリメントする
• Aの全要素をデクリメントする
• Aの1要素を選びK加算する
• Aの1要素を選びK減算する

Aの全要素がL以上U以下となるようにしたい。後ろ2つの加減算の使用回数の最小値を求めよ。

解法

全要素をインクリメント・デクリメントする代わりに、L,Uをデクリメント・インクリメントすると考えよう。
D=U-Lとすると、

• L未満のAの要素数が、L+Dより大きなAの要素数である

となるLの最大値をL'と置くと、最良のLはL'から±Kの範囲となる。

Aの各要素についてL=L'-KからL'+Kまで変化するとき、Kの加減算回数がどうなるかを求め、累積和で総和を取ろう。
その最小値が解。

ll N,K;
ll L,U;
ll A[202020];

ll sum[604040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L>>U;
	ll D=U-L;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	L=0;
	for(i=50;i>=0;i--) {
		ll TL=L+(1LL<<i);
		ll L1=lower_bound(A,A+N,TL)-A;
		ll R1=A+N-lower_bound(A,A+N,TL+D+1);
		if(L1<=R1) L=TL;
	}
	ll SL=max(0LL,L-K);
	
	FOR(i,N) {
		if(A[i]<=SL) {
			ll pat=(SL-A[i]+K-1)/K;
			sum[0]+=pat;
			int dif=K-(SL-A[i]+K-1)%K;
			sum[dif]++;
			sum[dif+K]++;
		}
		else if(A[i]<=SL+D) {
			sum[min(2*K+2,A[i]-SL+1)]++;
			sum[min(2*K+2,A[i]-SL+1+K)]++;
		}
		else {
			int d=(A[i]-(SL+D))%K;
			//d++;
			if(d==0) d=K;
			assert((A[i]-(SL+D)+K-1)/K>0);
			sum[0]+=(A[i]-(SL+D)+K-1)/K;
			sum[d]--;
			if((A[i]-(SL+D)+K-1)/K>1) sum[d+K]--;
			if(A[i]<=SL+2*K) {
				sum[A[i]-SL+1]++;
				sum[A[i]-SL+1+K]++;
			}
		}
		
	}
	ll mi=1LL<<60;
	FOR(i,2*K+1) {
		if(i) sum[i]+=sum[i-1];
		mi=min(mi,sum[i]);
	}
	cout<<mi<<endl;
	
	
	
}

まとめ

L'周辺にベストなLがある、って気づくところが難しい。