AtCoder Beginner Contest 137 C - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 137 に参加。
今日は A ~ C まで解いた。
C問題はかなりごり押しな実装をして解いてしまったけど、 解説動画で「mapを使うと簡単に実装できますよ」と教えてもらったので、 mapを使った実装方法を自分なりにまとめておく。
結果
- パフォーマンス:792
- レート:755 → 759 (+4)
C - Green Bin
N個の文字列が与えられる。
その中でアナグラムになっている文字列の組はいくつあるか。
参考
公式の解説動画を参考にしました。ありがとうございます。
map
mapはkeyとvalueをワンセットにして格納できる辞書みたいなデータ構造らしい。
とりあえず以下の記事を参考。
mapの利点はたくさんあるみたいで、 データの扱いやすさと探索の速さが特徴みたい。
私が一番驚いたことが、 存在しないkeyにアクセスすると、 自動でそのkeyが登録されるらしい。 自分で頑張ってそういう配列を実装しようとすると大変。
あと、for文を使ってmapにアクセスするときは以下の記事の内容も参考にしたい。
autoの話はこちらを参考。
コード
公式の解説動画を参考に書きました。ありがとうございます。
(スペースと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;
}