ABC137 C問題
問題文
文字列 に含まれる文字を何らかの順序で並べることで得られる文字列を の アナグラム と呼びます。
例えば、greenbin
は beginner
のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。
個の文字列 が与えられます。それぞれの文字列は長さが で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 の組であって、 が のアナグラムであるようなものの個数を求めてください。
制約
- は長さ の文字列である。
- の各文字は英小文字である。
- はすべて異なる。
解法の方針
- 入力文字列をsort
- mapを用いて同じものを数える
- それぞれの(count)(count-1)/2を計算する
- 10^5同士をかけるところでllにしないとオーバーフローする
解法1(map)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); ++i) int main() { int n; cin >> n; map<string, int> mp; rep(i, n) { string s; cin >> s; sort(s.begin(), s.end()); mp[s]++; //ない要素が来たら0初期化 } ll ans = 0; for (auto& p : mp) { int s = p.second; ans += (ll)s*(s - 1) / 2; } cout << ans << endl;
解法2(vector)
文字列を入れたvectorをsortして隣同士が一致するかどうか見る
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); ++i) int main(){ int n; cin>>n; vector<string> vec; rep(i,n){ string s; cin>>s; sort(s.begin(),s.end()); vec.push_back(s); } sort(vec.begin(),vec.end()); ll count=1; ll ans=0; rep(i,n-1){ if(vec[i]==vec[i+1]){ count++; }else{ ans+=count*(count-1)/2; count=1; } } ans+=count*(count-1)/2; cout<<ans<<endl; }
学んだもの
map-連想配列
1つ目の要素をキーにした配列
持っていないキーへの操作が来たら0初期化して追加してくれる
unordered-map
順番を気にしない代わりに速いmap
今回はこれでも通る
「組み合わせの数」の数え方
総数を数え上げ、(総数)(総数-1)/2を計算する
範囲for文
for(代入される変数 : 配列名)で書ける
続く{}内に代入される変数を書くことで、指定した配列の要素が順番に代入される
代入される変数の宣言規則は以下(下のURLより)
変数宣言 | e を変更可能か? | コンテナ内の要素を変更可能か? |
---|---|---|
const auto& e | No | No |
auto& e | Yes | Yes |
auto e | Yes | No |