ABC073-C 備忘録 p.25

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - Write and Erase

考察の流れ

N <= 10^5 なので、入力の都度試す方法だと間に合わない

A_i <= 10^9 なので、バケット法もあきらめる

となると、入力値をすべてソートして同じ値が奇数個存在したらカウント、でいけるだろうか

デバッグ用の配列サイズで提出していまい RE

コメント箇所で WA…
i<n で for 文を回していた
i<=n でないと最後の数値が奇数個あった場合にカウントできない

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;

int compare_ll(const void *a, const void *b){
   return *(ll*)a - *(ll*)b;
}

int main(){
   int n, ans=0;
   ll a[100001]={0};
   scanf("%d",&n);
   for(int i=0; i<n; i++){ scanf("%lld",&a[i]); }
   qsort( a, n, sizeof(ll), compare_ll );

   int cnt=1, tmp=a[0];
// for(int i=1; i<n; i++){
   for(int i=1; i<=n; i++){
       if( tmp==a[i] ){ cnt++; }
       else{
           if( cnt&1 ){ ans++; }
           tmp=a[i];
           cnt=1;
       }
   }
   printf("%d\n",ans);
   return 0;
}

まとめ

・サンプルを通しただけで投げない、本番だったらペナルティが痛い
　（と、以前も言っていた気がする）
・提出前に境界付近を必ず試すこと！
・デバッグ用のソースを投げない…

引き続き、のんびり精進します。

#note初心者 #備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語