はじめに

AtCoder Beginner Contest ( ABC ) 137 に参加。

今日は A ～ C まで解いた。

C問題はかなりごり押しな実装をして解いてしまったけど、解説動画で「mapを使うと簡単に実装できますよ」と教えてもらったので、 mapを使った実装方法を自分なりにまとめておく。

結果

パフォーマンス：792
レート：755 → 759 （+4）

C - Green Bin

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

その中でアナグラムになっている文字列の組はいくつあるか。

参考

公式の解説動画を参考にしました。ありがとうございます。

youtu.be

map

mapはkeyとvalueをワンセットにして格納できる辞書みたいなデータ構造らしい。

とりあえず以下の記事を参考。

qiita.com

mapの利点はたくさんあるみたいで、データの扱いやすさと探索の速さが特徴みたい。

私が一番驚いたことが、存在しないkeyにアクセスすると、自動でそのkeyが登録されるらしい。自分で頑張ってそういう配列を実装しようとすると大変。

あと、for文を使ってmapにアクセスするときは以下の記事の内容も参考にしたい。

cpprefjp.github.io

autoの話はこちらを参考。

prettysoft.hatenablog.com

コード

公式の解説動画を参考に書きました。ありがとうございます。

（スペースとtabが混ざってる気がする）

#include <iostream>
#include <string>
#include <map>    // mapのために必要
#include <algorithm>    // sortのために必要
using namespace std;
 
int main()
{
    int N;
    cin >> N;

    // "Key"は string, "Value"は long long int
    map<string, long long int> mp;

    for(int i = 0; i < N; i++)
    {
        string s;
        cin >> s;

        // 入力した文字列をソートしてKeyとして利用
        // ソートすればアナグラム同士の文字列は同じ文字列になる
        sort(s.begin(), s.end());

        // 文字列をKeyとしてmapに登録
        // 未登録の文字列Keyも自動で登録される（すごい）
        // 初期値は0になるので+1している
        // 同じ文字列の数を数えている
        mp[s]++;
    }
 
    long long int ans = 0;

    // mpの要素を一つずつ取り出していく
    for(auto& p : mp)
    {
        // Valueを取り出してkに入れる
        long long int k = p.second;
        // k個の中から2つ取り出す方法は```k×(k-1) / 2```通り
        ans += (long long int)(k * (k-1) / 2);
    }

    cout << ans << endl;

    return 0;
}