0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

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

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

N 個の文字列 s_1 , s_2 , … , s_N が与えられます。それぞれの文字列は長さが 10 で英小文字からなり、またこれらの文字列はすべて異なります。

二つの整数 i , j ( 1 ≤ i < j ≤ N ) の組であって、 s_i が s_j のアナグラムであるようなものの個数を求めてください。

2.制約

2 ≤ N ≤ 10⁵
s_i は長さ 10 の文字列である。
s_i の各文字は英小文字である。
s_1 , s_2 , … , s_N はすべて異なる。

3.入力例

入力

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa

出力

4.初見の感想

アナグラムをどう計算するか

→１文字ずつに分解し、ソートをして一致するかを調べる

5.学びポイント

一致した回数をどう保存するか

→Dictionary型で保存

6.コードと簡単な解説

using System;
using System.Collections.Generic;
 
public class Program{
    public static void Main(){
        int N=int.Parse(Console.ReadLine());
        long ans=0;
        var dict = new Dictionary<string, int>();
        for(int i=0;i<N;i++){
//入力を一文字ずつに分解しソート
            char[] a=Console.ReadLine().ToCharArray();
            Array.Sort(a);
            string s=new String(a);
//Dictionary型で一致するものがあるかを確認
            if(dict.ContainsKey(s)){
                ans+=dict[s];
                dict[s]++;
            }else{
                dict.Add(s,1);
            }
        }
//出力
        Console.WriteLine(ans);
    }
}

7.最後に

なかなかレートが伸び悩んでいます…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 137 C - Green Bin