問題概要
文字列の集合(要素数
)がある。
<
で、
番目の文字列が
番目の文字列のアナグラムになっている
の個数を求めよ。
atcoder.jp
解法
まず、各文字列をソートすることにより、任意の2つの文字列がアナグラムの関係にあるかどうかを高速に判定できる。
さらに、ソートした文字列の集合をソートすることにより、同じ文字列(アナグラムの関係にある文字列)の個数を高速に見ることができる。
もし、同じ文字列が
個あった場合、その中から2つの文字列を選ぶ方法は
個あるため、全体の集合を同じ文字列の集合に分解し、先程の数値を足してあげればよい。
atcoder.jp
