コンテンツにスキップ

DOJ Beginner Contest 11 D - Cipher Guess

サイト
DOJ
コンテスト
DOJ Beginner Contest 11
問題
D - Cipher Guess

英大文字だけからなる NN 個の暗号文の単語 C1,C2,…,CNC_1, C_2, \dots, C_N と、平文の単語 SS が与えられます。

単一換字式暗号(同じ文字は同じ文字に、異なる文字は異なる文字に置き換える)で SS を変換した結果になりうる単語を、候補とよびます。候補のうち暗号文に最も多く現れる単語を求める問題です。同数なら辞書順で最小のものを答え、候補がなければ -1 を出力します。

∣Ci∣,∣S∣≤20|C_i|, |S| \le 20 で、NN の総和は 10510^5 以下です。

単語 CC が候補であるための条件は、「SS で同じ文字が現れる位置の組」と「CC で同じ文字が現れる位置の組」が一致することです。

たとえば ABBA なら、A の位置が {0,3}\{0, 3\}、B の位置が {1,2}\{1, 2\} です。XYYX も {0,3},{1,2}\{0, 3\}, \{1, 2\} に分かれるので候補です。XYYY は {0},{1,2,3}\{0\}, \{1, 2, 3\} になるので候補ではありません。

そこで、各単語について文字ごとの出現位置のリストを作り、それをソートしたものを比べます。長さが違う単語は、位置の範囲が違うので自然に一致しません。

候補を Counter で数えます。あらかじめ CC を辞書順にソートしておくと、Counter には辞書順に単語が入ります。most_common は同数の要素を入れた順に返すので、most_common(1) で「最多で、同数なら辞書順最小」の単語が得られます。

単語の長さを LL とすると、全体で O(NL+Nlog⁡N)O(NL + N \log N) です。

Python
from collections import defaultdict, Counter
for _ in range(int(input())):
N = int(input())
C = input().split()
C.sort()
S = input()
d = defaultdict(list)
for i, a in enumerate(S):
d[a].append(i)
ans = Counter()
X = sorted(d.values())
for f in C:
d = defaultdict(list)
for i, a in enumerate(f):
d[a].append(i)
Y = sorted(d.values())
if X == Y:
ans[f] += 1
if ans:
print(ans.most_common(1)[0][0])
else:
print(-1)