問題はこちら
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) }