ABC137-C 備忘録 p.35

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

C - Green Bin

考察の流れ

バケットに入れる？
でも s_i の長さは10文字固定だから、バケットに入れなくてもよさそう

各文字列を取得時にソートして、さらにすべての文字列を辞書順に並べる

同じ文字列の個数をカウントし、nCr する

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;
ll _nCr(ll n, ll r){ if( n<r || n<0 || r<0 ){ return 0; } ll ans=1; if(r>(n-r)){ r=n-r; } for(ll i=1;i<=r;i++){ ans*=(n+1-i); ans/=i; } return ans; }

int small_2_large(const void *str1, const void *str2){
   return strcmp( (char*)str1, (char*)str2 );
}
int compare_char(const void *a, const void *b){
   return *(char*)a - *(char*)b;
}
int main(){
   int n,m;
   scanf("%d",&n);
   
   char s[100000][11]={0};
   for(int i=0;i<n;i++){
       scanf("%s", s[i]);
       qsort( s[i], 10, sizeof(char), compare_char );
   }
   qsort( s, n, sizeof(s[0]), small_2_large );
   
   ll cnt=1,ans=0,j=1;
   for(int idx=0;idx<n;idx+=j){
       cnt=1;
       j=1;
       while( memcmp(s[idx],s[idx+j],10)==0 ){
           cnt++;
           j++;
       }
       ans += _nCr(cnt,2);
   }
   printf("%lld\n",ans);
   return 0;
}

まとめ

・文字列の比較で手間取った
・発想までは良かったが、実装に時間をかけてしまったので反省

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

#備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語 #組み合わせ