[AtCoder] ABC 137 C – Green Bin

2019年8月10日

問題

方針

各文字列を構成する文字の種類と数が同じであれば、同じ文字列を構成できるので、文字列の文字を整列させマップなどでカウントすれば良いです。構成要素が同じ文字列の個数を \( v \) とすると、アナグラムの個数は、

\[ \dfrac{v (v – 1)}{2}\]

となります。これを足し上げていけば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  map<string, ll> m;
  string s;
  for (int i = 0; i < N; i++) {
    cin >> s;
    sort(s.begin(), s.end());
    m[s]++;
  }
  ll v = 0;
  for (auto it = m.begin(); it != m.end(); it++) {
    ll t = it->second;
    v += t * (t - 1) / 2;
  }
  cout << v << "\n";
  return 0;
}