コンテンツにスキップ

DOJ Starter Contest 1 F - 문자열 정렬하기

サイト
DOJ
コンテスト
DOJ Starter Contest 1
問題
F - 문자열 정렬하기

英小文字からなる NN 個の文字列が与えられます。文字列のスコアを、各文字の出現回数の二乗の和とします。例えば abaca のスコアは 32+12+12=113^2+1^2+1^2=11 です。

次の優先順位で文字列を並べ、11 行に 11 つずつ出力する問題です(N≤5×104N\le5\times10^4、各文字列の長さは 2020 以下)。

  1. スコアが小さい順
  2. 長さが短い順
  3. 辞書順

同じ文字列も、与えられた個数だけ出力します。

各文字列について、Counter で文字ごとの出現回数を数え、その二乗を足せばスコアを求められます。

あとは、ソートのキーとして (スコア, 長さ, 文字列) というタプルを返します。Python はタプルを先頭の要素から順に比較するので、問題で指定された優先順位をそのまま表せます。

S.sort(key=q) では各文字列に対して q が 11 回ずつ呼ばれ、その結果を使ってソートします。最大文字列長を LL とすると、キーの計算に O(NL)O(NL)、文字列の比較も含めたソートに O(NLlog⁡N)O(NL\log N) かかります。

Python
from collections import Counter
N = int(input())
S = [input() for i in range(N)]
def q(s):
c = Counter(s)
return (sum(i**2 for i in c.values()), len(s), s)
S.sort(key=q)
for s in S:
print(s)