ABC137 C問題 - 勉強記録

問題文

文字列 $a$ に含まれる文字を何らかの順序で並べることで得られる文字列を $a$ の アナグラム と呼びます。

例えば、greenbin は beginner のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。

$N$ 個の文字列 $s_{1}, s_{2}, \dots, s_{N}$ が与えられます。それぞれの文字列は長さが $10$ で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 $i, j$ $(1 \leq i < j \leq N)$ の組であって、 $s_{i}$ が $s_{j}$ のアナグラムであるようなものの個数を求めてください。

制約

$2 \leq N \leq 10^{5}$
$s_{i}$ は長さ $10$ の文字列である。
$s_{i}$ の各文字は英小文字である。
$s_{1}, s_{2}, \dots, s_{N}$ はすべて異なる。

解法の方針

入力文字列を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-連想配列

　１つ目の要素をキーにした配列

　持っていないキーへの操作が来たら0初期化して追加してくれる

unordered-map

　順番を気にしない代わりに速いmap

　今回はこれでも通る

「組み合わせの数」の数え方

　総数を数え上げ、(総数)(総数-1)/2を計算する

範囲for文

　for(代入される変数 : 配列名)で書ける

　続く{}内に代入される変数を書くことで、指定した配列の要素が順番に代入される

　代入される変数の宣言規則は以下（下のURLより）

変数宣言	e を変更可能か？	コンテナ内の要素を変更可能か？
const auto& e	No	No
auto& e	Yes	Yes
auto e	Yes	No

範囲for文 - cpprefjp C++日本語リファレンス