結果

問題 No.517 壊れたアクセサリー
ユーザー rpy3cpp
提出日時 2017-05-28 22:09:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 1,242 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-09-21 15:28:28
合計ジャッジ時間 1,371 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

def read_data():
    N = int(input())
    ns = [input() for _ in range(N)]
    M = int(input())
    ms = [input() for _ in range(M)]
    return N, M, ns, ms

def solve(N, M, ns, ms):
    pool = "".join(ns)
    LEN = sum(len(n) for n in ns)
    left = [set() for _ in range(26)]
    right = [set() for _ in range(26)]
    process(ns, left, right)
    process(ms, left, right)
    ans = [""] * 26
    for i in range(26):
        if chr(i + ord('A')) not in pool:continue
        fill(i, left)
        fill(i, right)
        if len(left[i]) + len(right[i]) != LEN - 1:
            return -1
        ans[len(left[i])] = chr(i + ord('A'))
    return ''.join(ans)
    

def process(ns, left, right):
    for word in ns:
        n = len(word)
        for i in range(n - 1):
            for j in range(i + 1, n):
                ci = ord(word[i]) - ord('A')
                cj = ord(word[j]) - ord('A')
                right[ci].add(cj)
                left[cj].add(ci)
    
def fill(i, left):
    stack = list(left[i])
    while stack:
        j = stack.pop()
        for k in left[j]:
            if k in left[i]:
                continue
            stack.append(k)
            left[i].add(k)

N, M, ns, ms = read_data()
print(solve(N, M, ns, ms))
0