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