Submission #34842713

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import itertools
import collections
N,M = map(int, input().split())
S = [str(input()) for _ in range(N)]
T = {str(input()) for _ in range(M)}
# N<=8で8!=40320通りなので全探索が間に合いそう
# が、間に入れる_のパターンもある。
# 最悪パターンはSが全部1文字だった時。
# Sの間7か所に、8個_を詰めるので重複組み合わせ7H8 = 3003通りなので
# 40320*3003 = 121080960 ≒ 10**8 なので間に合うか、合わないか微妙
# だが、NGパターンは10**5 までなので、試しているうちに必ずOKなパターンが出る
# ∴全パターンを試して、OKなのが出ればXを出力、NGならば-1を出力
char_len = sum([len(Si) for Si in S]) + N - 1   # Xの最短文字長さ。Sの合計文字長と各間に_が1個は入るのでその分
if char_len <= 16:
    # まずは最低限の_しか入れないパターンを試す
    for p in itertools.permutations(S,N):
        # p:文字の並び
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import itertools
import collections

N,M = map(int, input().split())
S = [str(input()) for _ in range(N)]
T = {str(input()) for _ in range(M)}

# N<=8で8!=40320通りなので全探索が間に合いそう
# が、間に入れる_のパターンもある。
# 最悪パターンはSが全部1文字だった時。
# Sの間7か所に、8個_を詰めるので重複組み合わせ7H8 = 3003通りなので
# 40320*3003 = 121080960 ≒ 10**8 なので間に合うか、合わないか微妙
# だが、NGパターンは10**5 までなので、試しているうちに必ずOKなパターンが出る
# ∴全パターンを試して、OKなのが出ればXを出力、NGならば-1を出力

char_len = sum([len(Si) for Si in S]) + N - 1   # Xの最短文字長さ。Sの合計文字長と各間に_が1個は入るのでその分

if char_len <= 16:
    # まずは最低限の_しか入れないパターンを試す
    for p in itertools.permutations(S,N):
        # p:文字の並び
        ans = list()
        for j in range(N-1):
            ans.append(p[j])
            ans.append("_")

        ans.append(p[N-1])  # 最後の文字は後ろに_入らないのでループから分ける
        ans = ''.join(map(str,ans))

        if ans in T:
            pass
        elif len(ans) >= 3:
            print(ans)
            exit()

    # _を入れる個数を限界まで試す
    for i in range(1,17 - char_len):
        # i:挿入する_の個数
        for p in itertools.permutations(S,N):
            # p:文字の並び
            for v in itertools.combinations_with_replacement([k for k in range(N-1)],i):
                # v:_の挿入箇所
                counted_v = collections.Counter(v)  # 挿入箇所毎に個数をまとめておく
                ans = list()
                for j in range(N-1):
                    ans.append(p[j])
                    ans.append("_")

                    if counted_v[j] != 0:
                        for k in range(counted_v[j]):
                            ans.append("_")
                
                ans.append(p[N-1])  # 最後の文字は後ろに_入らないのでループから分ける
                ans = ''.join(map(str,ans))

                if ans in T:
                    pass
                elif len(ans) >= 3:
                    print(ans)
                    exit()

    # 全部試してダメなら、ない。
    print(-1)
else:
    # そもそも試せるパターンがないので、ない。
    print(-1)

Submission Info

Judge Result