はまやんはまやんはまやん

hamayanhamayan's blog

Green Bin [AtCoder Beginner Contest 137 C]

https://atcoder.jp/contests/abc137/tasks/abc137_c

解説

https://atcoder.jp/contests/abc137/submissions/6894331

s[i]がs[j]のアナグラムである ⇔ ソート済みs[i]とソート済みs[j]が等しい
これを利用する。
これを考えると、s[i]をソートして、同じものはカウントしていく。
同じものの中で任意の2つがアナグラム関係にあるので、C(その個数,2)が条件を満たす組み合わせになる。
これをすべてのソート済みs[i]について行い、cnt*(cnt-1)/2の総和を取れば答え。

int N; string S[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];

    map<string, ll> cnt;
    rep(i, 0, N) {
        sort(all(S[i]));
        cnt[S[i]]++;
    }

    ll ans = 0;
    fore(p, cnt) ans += p.second * (p.second - 1) / 2;

    cout << ans << endl;
}