zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC137-C「Green Bin」です。
ポイント
大きなポイントは2つです。1つ目は，文字列をソートして考えることで「文字列を並び替えたもの」を同一視できるという点です。2つ目は，ソートされた文字列がそれぞれ何回出現するかをmap（もしくはunordered_map）を利用して管理するという点です。解答にあたっては，mapに保持された出現回数を$n$とおけば，
\begin{align}
{}_n C_{2}=\frac{1}{2}n(n-1)
\end{align}
{}_n C_{2}=\frac{1}{2}n(n-1)
\end{align}
をソートされた各文字列に対して計算していく必要がある点に注意です。そのまま$n$を足してしまうと誤解答になります。また，mapの各要素にアクセスするときは範囲for文を利用すると便利です。
おさえるべき内容
文字列をソートすることで並び替え問題を扱う
mapで出現頻度を管理する
出現頻度を組み合わせに変換する
範囲for文を利用してmapの各要素にアクセスする
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int main(){
int N;
cin >> N;
string S[N];
rep(i, N){
cin >> S[i];
}
rep(i, N){
// 各文字列をソートする
sort(S[i].begin(), S[i].end());
}
// long longでないと足りない
long long ans = 0;
// 出現頻度を保持するmap
map<string, long long> X;
// それぞれのソートされた文字列に対して出現頻度を管理する
rep(i, N){
X[S[i]]++;
}
// mapの各要素に対して範囲for文を利用する
for (auto x : X){
long long n = x.second;
ans += n * (n-1) / 2;
}
cout << ans << endl;
}mapをunordered_mapにすれば少し実行速度が上がります。これは，mapの内部構造が平衡二分探索木，unordered_mapの内部構造がハッシュテーブルを利用して実装されているためです。
コメント