問題はこちらです atcoder.jp
全列挙が間に合いそうなので、考えられる文字列を全列挙します。
全列挙にはDFSを使います（典型ですね）。
Sの並び替えはpermutationsを使い、"_"の追加をDFSでやります。
実装して以下のコードを提出してみます。
import sys,math
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10**7)
from collections import defaultdict,deque
from itertools import combinations,permutations,accumulate,product
from bisect import bisect,bisect_left,bisect_right
from heapq import heappop,heappush,heapify
#from sortedcontainers import SortedList,SortedSet
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def ms(): return map(int, input().split())
def li(): return list(map(int,input().split()))
#////////////////////////////
N,M = ms()
S = [input() for _ in range(N)]
T = set()
for _ in range(M):
t = input()
T.add(t)
def dfs(s,ind):
s += per[ind]
if len(s)>16: return
if ind==N-1:
if not s in T and 16>=len(s)>=3:
print(s)
exit()
return
for i in range(1,16-len(s)+1):
tmp = s + "_"*i
dfs(tmp,ind+1)
for per in permutations(S):
dfs("",0)
print(-1)
これを提出するとなんと3TLEになりました。
ざっとコードを見直しても計算量の見積もりが間違っているわけではなさそうです。
したがって、TLEの原因はPythonの再帰が遅いせいだと考えられます。
そこで、DFSを非再帰で書いてみます。
stackを使うとうまく書けます。（実装ではque=deque()としていますが、使い方としてはstackです）
import sys,math
from collections import defaultdict,deque
from itertools import combinations,permutations,accumulate,product
from bisect import bisect,bisect_left,bisect_right
from heapq import heappop,heappush,heapify
#from sortedcontainers import SortedList,SortedSet
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def ms(): return map(int, input().split())
def li(): return list(map(int,input().split()))
#////////////////////////////
N,M = ms()
S = [input() for _ in range(N)]
T = set()
for _ in range(M):
t = input()
T.add(t)
def dfs():
que = deque()
que.append(("",0))
while que:
s,ind = que.pop()
s += per[ind]
if len(s)>16: continue
if ind==N-1:
if not s in T and 16>=len(s)>=3:
print(s)
exit()
continue
for i in range(1,16-len(s)+1):
que.append((s+"_"*i,ind+1))
for per in permutations(S):
dfs()
print(-1)
これを提出すると1732msでACすることができました！！
やはり横着して再帰のまま提出するのはよくないですね。
非再帰DFSを書いたことがない方はそこから勉強してみるとよいと思います。
おまけ
PyPyの文字列連結はO(N)なので、s+"_"*iのところが少し遅くなっていそうです。
そこで、グローバルなリストは定義し、それを使ってDFSをしてみます。
これはDFSで帰りがけに処理をするのと同じ方法で実装できます。
def dfs():
que = deque()
que.append((0,0))
while que:
global s
ind,cnt = que.pop()
if ind==-1:
s.pop()
s.pop()
continue
s.append(per[ind])
cnt += len(per[ind])
if cnt>16: continue
if ind==N-1:
tmp = ''.join(s)
if not tmp in T and 16>=len(tmp)>=3:
print(tmp)
exit()
continue
for i in range(1,16-cnt+1):
s += ["_"]
que.append((-1,-1))
que.append((ind+1,cnt+i))
for per in permutations(S):
s = list()
dfs()
print(-1)
これを提出すると1505msとなり、少し高速になりました。
