ARC086-C 備忘録 p.32

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

C - Not so Diverse

考察の流れ

ボールの数字でバケットにいれて、同じ数字を持つボールの数を数える
最初から種類数が K 以下なら終了

同じ数字を持つボールの数が少ない順にソート

少ない順に、他の（例えば最も多くのボールに書かれた）数字に書き換える

書き換えるたびに、K 種類以下になったかを確認

#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b){
   return *(int*)a - *(int*)b;
}
int main(){
   int n,m,k,a[200001]={0},kind=0,cnt=0;
   scanf("%d%d",&n,&k);
   for(int i=0; i<n; i++){
       scanf("%d",&m);
       if(!a[m]){ kind++; }
       a[m]++;
   }
   if( kind <= k ){ printf("0\n"); return 0; }

   qsort( a, 200001, sizeof(int), compare_int );
   for(int i=0; i<200000; i++){
       if( a[i] ){ cnt+=a[i]; kind--; }
       if( kind <= k ){ break; }
   }
   printf("%d\n",cnt);
   return 0;
}

まとめ

・割と簡単に解法を思いつけた
・バケット法に慣れてきた気がする

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

#備忘録 #AtCoder #ARC #競技プログラミング #競プロ #C言語