読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.190 Dry Wet Moist

問題はこちら
No.190 Dry Wet Moist - yukicoder

全体をソートしておく
まずDry(和が負になるペア)を探すことを考える。
負の数は、絶対値が大きな方から貪欲に使うとして良い(和を負にしたいので、絶対値が大きな負の数を使わない理由はない)
負の数を1つ決めた時、ペアとなる正の数は、一番大きな数から順にやはり貪欲に使って良い(各負の数に対し、ギリギリまで大きな正の数を使うのが良いので)
Wet、Moistも同様。

a[1<<18];
c(int*a,int*b){return *a-*b;}
main(){
	int i,s,n,l,r;
	scanf("%d",&n);
	for(i=0;i<2*n;i++)scanf("%d",a+i);
	qsort(a,n*=2,4,c);

	//Dryを探す
	s=0;
	for(l=0,r=n-1;l<r;r--)if(a[l]<-a[r]){s++;l++;}
	//一番小さな値a[0]を選んで、それと組にしてDryになる物を大きな値の側から探してくる
	//Dryにできたらlは次へ、結果によらずrは次へ
	printf("%d ",s);

	//Wetも同様
	s=0;
	for(l=0,r=n-1;l<r;l++)if(a[l]>-a[r]){s++;r--;}
	printf("%d ",s);

	//Moistもやるべき事は同じだが、lとrのどちらを進めるかを考える必要がある
	s=0;
	for(l=0,r=n-1;l<r;){
		if(a[l]==-a[r]){s++;l++;r--;}
		else if(a[l]+a[r]<0)l++;
		else r--;
	}
	printf("%d",s);
	return 0;
}

DryとWetだけなら、ループの部分は

#define f(P,Q,R)for(l=0,r=n-1;l<r;P)a[l]Q-a[r]?s++,R:0;
f(r--,<,l++)
f(l++,>,r--)

とそれぞれまとめられる。
なので、Moistもこの形になるように変形することを考えると

//l,rを動かすタイミングを変える
for(l=0,r=n-1;l<r;){
	a[l]==-a[r]?s++:0;
	a[l]+a[r]<=0?l++,a[l]==-a[r]?r--:0:r--;
}
//↓
for(l=0,r=n-1;l<r;a[l]+a[r]<=0?r-=a[l++]==-a[r]:r--;)a[l]==-a[r]?s++:0;

とできる。
また、nをaにまとめて読み込んで短縮することで、最終的に次を得る

#define f(P,Q,R)for(l=0,r=~n;l<r;P)a[l]Q-a[r]?s++,R:0;s=!printf("%d ",s);
a[1<<18],s,r;
c(int*p,int*q){r=*p-*q;}
main(n,l){
	for(;~scanf("%d",a-n--););
	qsort(a,-++n,4,c);
	f(r--,<,l++)
	f(l++,>,r--)
	f(a[l]+a[r]<=0?r-=a[l++]==-a[r]:r--,==,0)
}

231B

16/07/31追記
lの初期値を0にしておくことで2B短縮

#define f(P,Q,R)for(l=0,r=~n;l<r;P)a[l]Q-a[r]?s++,R:0;s=!printf("%d ",s);
#define f(P,Q,R)for(r=~n;l<r;P)a[l]Q-a[r]?s++,R:0;l=s=!printf("%d ",s);

さて、moistのところをどうにかして短くしたい
上ではr-=a[l++]==-a[r]と、a[l]==a[r]の判定をもう1回しているので、ここは直前の部分を再利用することで短縮できる

#define f(P,Q,R)for(r=~n;l<r;P)x=a[l]Q-a[r]?s++,R:0;l=s=!printf("%d ",s);
//この部分で+2B、新しい変数を使ったので+2B
f(a[l]+a[r]<=0?r-=++l&&x:r--,==,1)
//7B短縮
//f(a[l]+a[r]<=0?r-=x,++l:r--,==,1)とすると引数が4つと見なされてエラー

あわせて5B短縮の226B

#define f(P,Q,R)for(r=~n;l<r;P)x=a[l]Q-a[r]?s++,R:0;l=s=!printf("%d ",s);
a[1<<18],s,l,r,x;
c(int*p,int*q){r=*p-*q;}
main(n){
	for(;~scanf("%d",a-n--););
	qsort(a,-++n,4,c);
	f(r--,<,l++)
	f(l++,>,r--)
	f(a[l]+a[r]<=0?r-=++l&&x:r--,==,1)
}

2016/10/16追記
Moistの部分にまだ無駄があるようにみえる

f(a[l]+a[r]<=0?r-=++l&&x:r--,==,1)
f(r-=a[l]+a[r]<=0?++l&&x:1,==,1)
f(r-=a[l]+a[r]>0?:++l&&x,==,1)

++l&&xの部分を1B縮めたい。
xに代入される値はfの第三引数だから、これをlにすればl/l++とかでいける
……と思ったけど、これだと最初l=0のときに0除算でREになる。
じゃあlとrを入れ替えよう

f(r-=a[l]+a[r]>0?:++l&&x,==,1)
f(l+=a[l]+a[r]<0?:--r&&x,==,1)
f(l+=a[l]+a[r]<0?:x/r--,==,r)

ということでトータル5B短縮の221B

#define f(P,Q,R)for(r=~n;l<r;P)x=a[l]Q-a[r]?s++,R:0;l=s=!printf("%d ",s);
a[1<<18],s,l,r,x;
c(int*p,int*q){r=*p-*q;}
main(n){
	for(;~scanf("%d",a-n--););
	qsort(a,-++n,4,c);
	f(r--,<,l++)
	f(l++,>,r--)
	f(l+=a[l]+a[r]<0?:x/r--,==,r)
}


2016/12/03追記
自明な1B

#define f(P,Q,R)for(r=~n;l<r;P)x=a[l]Q-a[r]?s++,R:0;l=s=!printf("%d ",s);
a[1<<18],s,l,r,x;
c(int*p,int*q){r=*p-*q;}
main(n){
	for(;~scanf("%d",a-n--););
	qsort(a,-++n,4,c);
	f(r--,<,l++)
	f(l++,>,r--)
	f(l+=a[l]<-a[r]?:x/r--,==,r)
}