メモ

yukicoderでゆるふわgolf

yukicoder No.182 新規性の虜

問題はこちら
No.182 新規性の虜 - yukicoder

a[i]の値が大きいので「各数が何回現れたか」を(そのまま)保存するのはちょっと厳しそう
C++ならmapですむ話なのだが)
ということで次のような方針

a[i]をソートする
前後どちらとも異なっていれば新規性のある数であり、一致していれば重複しているので新規性はない

c(int*a,int*b){return*a-*b;}
int main(){
	int n,i,s,a[100010]={};
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	//配列に1から読み込んだ
	qsort(a+1,n,4,c);
	s=0;
	for(i=1;i<=n;i++)if(a[i-1]!=a[i]&&a[i]!=a[i+1])s++;
	//a[0]とa[n+1]は0であり、与えられた数は非0であることを利用している
	printf("%d",s);
	return 0;
}

これで縮める

x,n,s,a[1<<17];
c(int*a,int*b){x=*a-*b;}
main(){
	for(;~scanf("%d",a+n);n++);
	for(qsort(a+1,n,4,c);--n;s+=a[n]-a[n+1]&&a[n+1]-a[n+2]);
	//qsortが行われる時点で変数nはN+1にっているので
	//ソート後にはa[1]が0となり、a[2]~a[N+1]にもとの数値たちが入る
	s=!printf("%d",s);
}

ポインタを使って短縮

x,s,a[1<<17],*p=a;
c(int*a,int*b){x=*a-*b;}
main(){
	for(;~scanf("%d",p);p++);
	for(qsort(a+1,p-a,4,c);--p-a;s+=*p-p[1]&&p[1]-p[2]);
	s=!printf("%d",s);
}

145B


2017/07/29追記
コンパイラのバージョンアップによる高速化で、以前はTLEだったO(N^2)解法がACになっていた(!)

a[1<<17],n,k,s;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
		k=0;
		for(int j=0;j<i;j++)if(a[i]==a[j])k++;
		if(k==0)s++;
		else if(k==1)s--;
	}
	printf("%d",s);
}

ということで、これをぎゅっと縮める

i,j,s,a[1<<17];
main(k){
	for(;~scanf("%d",a+i);s-=1/k*3-2/k,i++)for(k=j=1;j<i;j++)k+=a[i]==a[j];
	printf("%d",~s);
}

111B
for文を圧縮するとTLEになる

i,j,s,a[1<<17];
main(k){
	for(;++j<i?k+=a[i]==a[j]:(s+=1/k*3-2/k,k=j=1,~scanf("%d",++i+a)););
	printf("%d",s-2);
}