メモ

yukicoderでゆるふわgolf

yukicoder No.198 キャンディー・ボックス2

問題はこちら
No.198 キャンディー・ボックス2 - yukicoder

手持ちのキャンディの数に制限がないとする
このとき問題は「Σ|c[i]-m|を最小化するmを求めよ」と読み替えられるので、mはc[i]の中央値とすれば良い。
(証明)
c[i]の中央値をmとし、αを任意にとる。必要なら全体を-1倍することでm≦αとしてよい。
m<c[i]のとき三角不等式 ||c[i]-m|-|c[i]-α||≦|α-m| より |c[i]-α|≧|c[i]-m|-(α-m)
c[i]≦mのとき|c[i]-α|=|c[i]-m|+(α-m)
よってε=α-mとおけば
Σ|c[i]-α|≧Σ|c[i]-m|+ε(#{i|c[i]≦m}-#{i|c[i]≦m})
となる。中央値の定義から第2項のカッコ内は0以下であり、m≦αだったのでε≧0であるから
Σ|c[i]-α|≧Σ|c[i]-m| が成立する
(証明終)
手持ちのキャンディに制限があるとき、最終的な1箱あたりの個数は(B+Σc[i])/N以下でなければならないので、結局求める答えはmin( (B+Σc[i])/N,median(c[i]))となる

ところで上の証明をよく読むと、N=2kのとき、丁寧にk番目とk+1番目を足して2でわらなくても、その間(境界含む)にある値ならばなんでも良いことがわかる
(値がεだけ変化した時、c[i]<mなら|c[i]-m|に比べて値がε大きく、c[i]>mならε小さくなり、中央値の定義からそれぞれの個数は同じ)

int c(int*a,int*b){return*a-*b;}
int main(){
	long b,s=0;
	int n,i,a[11];
	scanf("%ld%d",&b,&n);
	for(i=0;i<n;i++){
		scanf("%d",a+i);
		b+=a[i];
	}
	qsort(a,n,4,c);
	b/=n;
	b=b<a[n/2]?b:a[n/2];
	for(i=0;i<n;i++)s+=labs(b-a[i]);
	printf("%ld",s);
}

読み飛ばしを工夫したり配列サイズをごまかしたり型をごまかしたりといつもの短縮をして終わり

long s,q;
x,j=-2,a[9];
c(int*a,int*b){x=*a-*b;}
main(i){
	for(;~scanf("%d",a+j);q+=++j?a[j-1]:0);
	qsort(a,j,4,c);
	for(i=q/j<(i=a[j/2])?q/j:i;j--;s+=abs(a[j]-i));
	//制約上i<1e9となっているのでlabsでなくabsでよい
	j=!printf("%ld",s);
}

174B