AtCoder ABC 137 C - Green Bin (4Q, 茶色, 300 点)

すごく面白い問題！

• 問題へのリンク

問題概要

個の文字列 が与えられる。

これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。

制約

• 

考えたこと

まずは、問題の条件をわかりやすく言い換えることを考えよう。つまり、「2 つの文字列 が互いにアナグラムである」という条件は複雑なので、これをわかりやすく言い換えたいのだ。

互いにアナグラムかどうかを判定する簡単な方法として、

---

をアルファベット順にソートして、一致するかどうかを調べる

---

というものがある。これに気づきさえすれば、あとは簡単だ。与えられた各文字列 について、それぞれソートしておく。そうした上で、次の連想配列を定義しよう。

---

nums[str]：文字列 のうち、ソート後の文字列が str であるようなものの個数

---

これさえ求まれば、あとは、各文字列 str に対して、その個数を として

を足していけば良い。

計算量は。文字列 の長さの最大値を として、 となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N;

    map<string, long long> nums;
    for (int i = 0; i < N; i++) {
        cin >> S;
        sort(S.begin(), S.end());
        nums[S]++;
    }

    long long res = 0;
    for (auto [str, num] : nums) {
        res += num * (num - 1) / 2;
    }
    cout << res << endl;
}