DOJ Beginner Contest 11 D - Cipher Guess
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 11
- 問題
- D - Cipher Guess
英大文字だけからなる 個の暗号文の単語 と、平文の単語 が与えられます。
単一換字式暗号(同じ文字は同じ文字に、異なる文字は異なる文字に置き換える)で を変換した結果になりうる単語を、候補とよびます。候補のうち暗号文に最も多く現れる単語を求める問題です。同数なら辞書順で最小のものを答え、候補がなければ -1 を出力します。
で、 の総和は 以下です。
候補かどうかの判定
Section titled “候補かどうかの判定”単語 が候補であるための条件は、「 で同じ文字が現れる位置の組」と「 で同じ文字が現れる位置の組」が一致することです。
たとえば ABBA なら、A の位置が 、B の位置が です。XYYX も に分かれるので候補です。XYYY は になるので候補ではありません。
そこで、各単語について文字ごとの出現位置のリストを作り、それをソートしたものを比べます。長さが違う単語は、位置の範囲が違うので自然に一致しません。
最多の候補を選ぶ
Section titled “最多の候補を選ぶ”候補を Counter で数えます。あらかじめ を辞書順にソートしておくと、Counter には辞書順に単語が入ります。most_common は同数の要素を入れた順に返すので、most_common(1) で「最多で、同数なら辞書順最小」の単語が得られます。
単語の長さを とすると、全体で です。
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)