結果

問題 No.517 壊れたアクセサリー
ユーザー rpy3cpprpy3cpp
提出日時 2017-05-28 22:09:29
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 1,242 bytes
コンパイル時間 525 ms
コンパイル使用メモリ 12,112 KB
実行使用メモリ 10,272 KB
最終ジャッジ日時 2023-10-21 14:13:56
合計ジャッジ時間 1,497 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
10,256 KB
testcase_01 AC 29 ms
10,256 KB
testcase_02 AC 29 ms
10,256 KB
testcase_03 AC 30 ms
10,260 KB
testcase_04 AC 31 ms
10,256 KB
testcase_05 AC 30 ms
10,256 KB
testcase_06 AC 29 ms
10,256 KB
testcase_07 AC 29 ms
10,256 KB
testcase_08 AC 31 ms
10,256 KB
testcase_09 AC 30 ms
10,256 KB
testcase_10 AC 30 ms
10,256 KB
testcase_11 AC 29 ms
10,256 KB
testcase_12 AC 30 ms
10,264 KB
testcase_13 AC 30 ms
10,264 KB
testcase_14 AC 31 ms
10,268 KB
testcase_15 AC 31 ms
10,268 KB
testcase_16 AC 30 ms
10,256 KB
testcase_17 AC 31 ms
10,256 KB
testcase_18 AC 31 ms
10,272 KB
権限があれば一括ダウンロードができます

ソースコード

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