Problem:


Score : 500 points

Problem Statement

Snuke has a string s.
From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c.
Find the minimum possible length of s.

Constraints

1 \leq |a|, |b|, |c| \leq 2000

a, b, and c consists of lowercase English letters and ?s.

Input

Input is given from Standard Input in the following format:

a
b
c

Output

Print the minimum possible length of s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.



Sample input:
a?c
der
cod


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            li = len(s[i])
            di = d[i]
            for j in range(i, 3):
                lj = len(s[j])
                dij = di[j]
                for k in range(li):
                    notok = False
                    for ni in range(k, li):
                        nj = ni - k
                        if nj >= lj:
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            notok = True
                    dij[k] = notok
        f = lambda i, j, k: False if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if f(0, 1, x):
                    continue
                if f(1, 2, y):
                    continue
                if f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                if ans > now:
                    ans = now
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
for i in range(160*(10**5)):
    print(i)

Submission status: Time Limit Exceeded

Solution code:
for i in range(160*10**5):
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

A = input()
B = input()
C = input()
la, lb, lc = len(A), len(B), len(C)
a = "?" * (lb+lc) + A + "?" * (lb+lc)

def Same(x, y, z):
	for i in range(len(x)):
		if x[i] != y[i] and x[i] != "?" and y[i] != "?":
			return False
		if y[i] != z[i] and y[i] != "?" and z[i] != "?":
			return False
		if z[i] != x[i] and z[i] != "?" and x[i] != "?":
			return False
	return True

ans = la+lb+lc
for i in range(la+lb+lc+lc+1):
	b = "?" * i + B + "?" * (la+lb+lc+lc-i)
	for j in range(la+lb+lc+lb+1):
		c = "?" * j + C + "?" * (la+lb+lc+lb-j)
		
		if Same(a, b, c):
			res = max(i+lb, la+lb+lc, j+lc) - min(i, lb+lc, j)
			ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  a = list(input())
  b = list(input())
  c = list(input())
  ab = [False]*20000
  ac = [False]*20000
  bc = [False]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  a = input()
  b = input()
  c = input()
  ab = [False]*17000
  ac = [False]*17000
  bc = [False]*17000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+8500]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+8500]))and(not(ac[j+8500]))and(not(bc[j-i+8500])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
  
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  a = input()
  b = input()
  c = input()
  ab = [False]*20000
  ac = [False]*20000
  bc = [False]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
  
main()

Submission status: Time Limit Exceeded

Solution code:
def solve_panasonic2020_e():
    from itertools import islice, permutations, zip_longest

    def cv2num(c):
        return -1 if c == '?' else ord(c)

    *a, = map(cv2num, input())
    *b, = map(cv2num, input())
    *c, = map(cv2num, input())

    abc = a, b, c

    ret = sum(map(len, abc))
    for perm in permutations(abc):
        first, second, third = perm

        cands = [first + second]
        for i in range(len(first)):
            # first[i:]とsecondが一致するか見る
            # 一致なら候補に残す
            # すべてダメならfirst+secondだけ候補になる(重なりなし)
            cand = []
            for fc, sc in zip_longest(islice(first, i, len(first)), second, fillvalue=0):
                if not (fc and sc):
                    cand.append(fc + sc)
                elif fc == sc or sc == -1:
                    cand.append(fc)
                elif fc == -1:
                    cand.append(sc)
                else:
                    break
            else:
                cand = first[:i] + cand
                cands.append(cand)

        for cand in cands:
            for i in range(len(cand)):
                t = i
                for cc, tc in zip_longest(islice(cand, i, len(cand)), third, fillvalue=0):
                    t += 1
                    if not (cc and tc):
                        continue
                    if not (cc == tc or cc == -1 or tc == -1):
                        break

                else:
                    ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    solve_panasonic2020_e()

Submission status: Time Limit Exceeded

Solution code:
def solve_panasonic2020_e():
    from itertools import islice, permutations, zip_longest

    abc = tuple(input() for _ in range(3))

    ret = sum(map(len, abc))
    for perm in permutations(abc):
        first, second, third = perm

        cands = [first + second]
        for i in range(len(first)):
            # first[i:]とsecondが一致するか見る
            # 一致なら候補に残す
            # すべてダメならfirst+secondだけ候補になる(重なりなし)
            cand = ''
            for fc, sc in zip_longest(islice(first, i, len(first)), second, fillvalue=''):
                if not fc or not sc:
                    cand += fc + sc
                elif fc == sc or sc == '?':
                    cand += fc
                elif fc == '?':
                    cand += sc
                else:
                    break
            else:
                cand = first[:i] + cand
                cands.append(cand)

        for cand in cands:
            for i in range(len(cand)):
                t = i
                for cc, tc in zip_longest(islice(cand, i, len(cand)), third, fillvalue=''):
                    t += 1
                    if not cc or not tc:
                        continue
                    if not (cc == tc or cc == '?' or tc == '?'):
                        break

                else:
                    ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    solve_panasonic2020_e()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    S = [rs() for _ in range(3)]
    mi = len(S[0]) + len(S[1]) + len(S[2])
    L = [[set() for i in range(3)] for j in range(3)]
    
    for i in range(3):
        for j in range(3):
            if(i == j): continue
            s = S[i]
            t = S[j]
            for k in range(-len(t), len(s) + 1):
                chk = True
                for l in range(len(s)):
                    ti = l - k
                    if(ti < 0 or ti >= len(t)): continue
                    if(s[l] == t[ti]): continue
                    if(s[l] == '?'): continue
                    if(t[ti] == '?'): continue
                    chk = False
                    break
                if(chk): L[i][j].add(k)
    a = [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]
    for ord in a:
        i = ord[0]
        j = ord[1]
        k = ord[2]
        la = 0
        ra = len(S[i])
        for ij in L[i][j]:
            lb = ij
            rb = ij + len(S[j])
            for ik in L[i][k]:
                lc = ik
                rc = ik + len(S[k])
                if lb <= lc and lc < rb:
                    if not ((lc - lb) in L[j][k]): continue
                if lc <= lb and lb < rc:
                    if not ((lb - lc) in L[k][j]): continue
                l = min(la, lb)
                l = min(l, lc)
                r = max(ra, rb)
                r = max(r, rc)
                mi = min(mi, r - l)
    
    print(mi)
                


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  ab = len(a)+len(b)
  abc = float("inf")
  for d in merge(a,b):
    if len(d) > abc:
      break
    l = len(next(merge(d, c)))
    abc = min(abc, l)
  if abc <= ab:
    return abc
  
  for i in range(1,min(len(c),abc-ab)):
    for j in range(1,len(c)):
      if comp(a[-j:]+"?"*i+b, c):
        return ab+i
      if comp(b[-j:]+"?"*i+a, c):
        return ab+i
  return abc

a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
A=input()
B=input()
C=input()

a,b,c=len(A),len(B),len(C)

def f(X,Y):
  XY=[True]*(10**4)
  x,y=len(X),len(Y)
  for i in range(5000-y+1,5000+x):
    ret=True
    if i<=5000:
      for j in range(min(x,y+i-5000)):
        if X[j]=="?" or Y[j-i+5000]=="?" or X[j]==Y[j-i+5000]:
          continue
        else:
          ret=False
    else:
      for j in range(min(y,x-i+5000)):
        if Y[j]=="?" or X[j+i-5000]=="?" or Y[j]==X[j+i-5000]:
          continue
        else:
          ret=False
    XY[i]=ret
  return XY
AB=f(A,B)
BC=f(B,C)
AC=f(A,C)
ans=a+b+c
for i in range(5000-b-c,5000+a+c):
  for j in range(5000-b-c,5000+a+b):
    if -4000<=j-i<=4000:
      if AB[i] and AC[j] and BC[j-i+5000]:
        l=min(5000,i,j)
        r=max(i+b,j+c,5000+a)
        ans=min(ans,r-l)
    else:
      if AB[i] and AC[j]:
        l=min(5000,i,j)
        r=max(i+b,j+c,5000+a)
        ans=min(ans,r-l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()


def func(a, b):
    p = len(a)
    q = len(b)
    for i in range(p):
        f = 0
        z = min(q, p - i)
        for j in range(z):
            if a[j + i] != "?" and b[j] != "?" and a[j + i] != b[j]:
                break
            f += 1
        if f == z:
            return max(p, q + i)
    return p + q


def func2(a, b, i):
    p = len(a)
    q = len(b)
    f = 0
    z = min(q, p - i)
    for j in range(z):
        if a[j + i] != "?" and b[j] != "?" and a[j + i] != b[j]:
            break
        f += 1
    if f == z:
        return True
    return False


def func3(a, b, i):
    p = len(a)
    q = len(b)
    res = []
    for j in range(i):
        res.append(a[j])
    if p >= q + i:
        for j in range(q):
            if a[i + j] == "?":
                res.append(b[j])
            else:
                res.append(a[i + j])
        for j in range(q + i, p):
            res.append(a[j])
    elif p == q + i:
        for j in range(q):
            if a[i + j] == "?":
                res.append(b[j])
            else:
                res.append(a[i + j])
    else:
        for j in range(p - i):
            if a[i + j] == "?":
                res.append(b[j])
            else:
                res.append(a[i + j])
        for j in range(p - i, q):
            res.append(b[j])
    return "".join(map(str, res))


def func4(a, b, c):
    res = func(a + b, c)
    for i in range(len(a)):
        if func2(a, b, i):
            p = func3(a, b, i)
            res = min(res, func(p, c))
    return res


res = 10 ** 8
res = min(res, func4(a, b, c))
res = min(res, func4(a, c, b))
res = min(res, func4(b, a, c))
res = min(res, func4(b, c, a))
res = min(res, func4(c, a, b))
res = min(res, func4(c, b, a))
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
a = input()
b = input()
c = input()


def match(c1, c2):
    return c1 == "?" or c2 == "?" or c1 == c2


offset = 10 ** 5 // 2
limit = 2000

ab = [True] * (10 ** 5)
ac = [True] * (10 ** 5)
bc = [True] * (10 ** 5)

for i in range(len(a)):
    for j in range(len(b)):
        if not match(a[i], b[j]):
            ab[i - j + offset] = False

for i in range(len(a)):
    for j in range(len(c)):
        if not match(a[i], c[j]):
            ac[i - j + offset] = False

for i in range(len(b)):
    for j in range(len(c)):
        if not match(b[i], c[j]):
            bc[i - j + offset] = False

ans = 3 * limit
for i in range(-2 * limit, 2 * limit + 1):
    for j in range(-2 * limit, 2 * limit + 1):
        if ab[i + offset] and ac[j + offset] and bc[j - i + offset]:
            left = min(0, i, j)
            right = max(len(a), len(b) + i, len(c) + j)
            ans = min(ans, right - left)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

A,B,C = read().decode().split()

A = np.array(list(A))
B = np.array(list(B))
C = np.array(list(C))

M = 2020

def can_match(x,y):
    L = min(len(x), len(y))
    x = x[:L]
    y = y[:L]
    return np.all((x == '?') | (y == '?') | (x == y))

def solve(A,B,C,LA,LB,LC):
    BA = [True] * (M)
    for i in range(M):
        BA[i] = can_match(A[i:], B)
    CA = [True] * (M+M)
    for i in range(M+M):
        CA[i] = can_match(A[i:], C)
    CB = [True] * (M)
    for i in range(M):
        CB[i] = can_match(B[i:], C)
    BA = np.array(BA)
    CA = np.array(CA)
    CB = np.array(CB)
    k = np.arange(M)[:,None] + np.arange(M)[None,:]
    cond = BA[:,None] & CB[None,:] & CA[k]
    length = np.maximum(LA, np.maximum((LB + np.arange(M))[:,None], (LC + k)))
    return length[cond].min()

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = solve(A,B,C,LA,LB,LC)
    if answer > x:
        answer = x
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def match(x, y):
    return x == y or x == '?' or y == '?'


def check(s, t):
    ANS = [1] * (10 ** 5)
    S = len(s); T = len(t)
    for i in range(S):
        for j in range(T):
            if not match(s[i], t[j]):
                ANS[i - j + 50000] = 0
    return ANS


a = input()
b = input()
c = input()
lenA = len(a)
lenB = len(b)
lenC = len(c)

AB = check(a, b)
AC = check(a, c)
BC = check(b, c)

ans = lenA + lenB + lenC
M = ans
for i in range(-2 * M, 2 * M + 1):
    for j in range(-2 * M, 2 * M + 1):
        if AB[i + 50000] and AC[j + 50000] and BC[j - i + 50000]:
            L = min(0, min(i, j))
            R = max(lenA, max(lenB + i, lenC + j))
            ans = min(ans, R - L)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for m, lr in merge2(a,b):
    yield m

def merge2(a,b,lr=None):
  for i in range(1,len(b)):
    if lr!=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], 1
    if lr!=1:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], 0
  yield a+b, 0
  yield b+a, 1

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d, lr in merge2(a,c):
  if len(d) > abc:
    break
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)

Submission status: Time Limit Exceeded

Solution code:
def _comp(a,b):
  for x,y in zip(a,b):
    if x==y or y=="?":
      yield x
    elif x=="?":
      yield y
    else:
      return

def comp(a,b):
  m = "".join(_comp(a,b))
  if min(len(a),len(b)) == len(m):
    return m
  else:
    return False

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d in merge(a,c):
  if len(d) > abc:
    break
  l = len(next(merge(d, b)))
  abc = min(abc, l)

print(abc)

Submission status: Time Limit Exceeded

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d in merge(a,c):
  if len(d) > abc:
    break
  l = len(next(merge(d, b)))
  abc = min(abc, l)

print(abc)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = max(len(a),len(b),len(c))
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M*2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[j-i + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = max(len(a),len(b),len(c))
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M+2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[j-i + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d in merge(a,c):
  if len(d) > abc:
    break
  l = len(next(merge(d, b)))
  abc = min(abc, l)

for d in merge(b,c):
  if len(d) > abc:
    break
  if len(a) < len(d):
    l = len(next(merge(d, a)))
  else:
    l = len(next(merge(a, d)))
  abc = min(abc, l)

print(abc)

Submission status: Time Limit Exceeded

Solution code:
def match(x, y, lx, ly, ix, iy):
  minimum = min(ix + lx, iy + ly)
  if ix <= iy:
    d = iy - ix
    for i in range(minimum - iy):
      if x[i+d] != '?' and y[i] != '?' and x[i+d] != y[i]:
        return False
    return True
  d = ix - iy
  for i in range(minimum - ix):
    if x[i] != '?' and y[i+d] != '?' and x[i] != y[i+d]:
      return False
  return True

a = input()
b = input()
c = input()

la = len(a)
lb = len(b)
lc = len(c)

ia = 2000
minimum = 6000
for ib in range(4001):
  for ic in range(4001):
    ab = match(a, b, la, lb, ia, ib)
    bc = match(b, c, lb, lc, ib, ic)
    ca = match(c, a, lc, la, ic, ia)
    if ab and bc and ca:
      tmp = max(ia + la, ib + lb, ic + lc) - min(ia, ib, ic)
      if tmp < minimum:
        minimum = tmp
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = 2000
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M+2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[i-j + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
a = list(input())
b = list(input())
c = list(input())
w = [a, b, c]

ans = 10000

for x in itertools.permutations(range(3), 3):
    l0 = len(w[x[0]])
    l1 = len(w[x[1]])
    l2 = len(w[x[2]])
    
    for i in range(l0+1):
        for j in range(l1+1):
            org = [-1]*(l0+l1+l2)
            error = False

            for k in range(l0):
                org[k] = w[x[0]][k]
            for k in range(l1):
                if org[i+k] == '?' or org[i+k] == -1 or org[i+k] == w[x[1]][k]:
                    org[i+k] = w[x[1]][k]
                else:
                    error = True
                    break
            for k in range(l2):
                if org[i+j+k] == '?' or org[i+j+k] == -1 or org[i+j+k] == w[x[2]][k]:
                    org[i+j+k] = w[x[2]][k]
                else:
                    error = True
                    break
            if not error:
                if -1 in org:
                    tmp = org.index(-1)
                else:
                    tmp = len(org)
                ans = min(ans, tmp)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def cmp1(a,b,stt):
    l = []
    for i in range(stt,len(a)):
        ok = True
        for j in range(min(len(b),len(a)-i)):
            #ddprint("a {} b {} i {} j {}".format(a,b,i,j))
            #ddprint("aij {} bj {}".format(a[i+j],b[j]))
            if a[i+j]!='?' and b[j]!='?' and a[i+j]!=b[j]:
                ok = False
                break
        if ok:
            l.append(i)
    #ddprint("cmp1 a {} b {} l {}".format(a,b,l))
    return l

def cmp(a,b):
    l1 = cmp1(a,b,0)
    l2 = cmp1(b,a,1)
    return (l1,l2)

a = ins()
b = ins()
c = ins()
la = len(a)
lb = len(b)
lc = len(c)
ab = cmp(a,b)
ac = cmp(a,c)
bc = cmp(b,c)
ddprint(ab)
ddprint(ac)
ddprint(bc)
ba = (ab[1],ab[0])
ca = (ac[1],ac[0])
cb = (bc[1],bc[0])
mn = la+lb+lc
for p in [0,1]:
 for q in [0,1]:
  for ii in ab[p]:
    i = ii if p==0 else -ii
    for jj in ac[q]:
        j = jj if q==0 else -jj
        if lc+j<=i or lb+i<=j or (j-i) in bc[0] or (i-j) in bc[1]:
            v = max([la,lb+i,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for p in [0,1]:
 for q in [0,1]:
  for ii in ba[p]:
    i = ii if p==0 else -ii
    for jj in bc[q]:
        j = jj if q==0 else -jj
        if lc+j<=i or la+i<=j or (j-i) in ac[0] or (i-j) in ac[1]:
            v = max([la+i,lb,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for p in [0,1]:
 for q in [0,1]:
  for ii in ca[p]:
    i = ii if p==0 else -ii
    for jj in cb[q]:
        j = jj if q==0 else -jj
        if lb+j<=i or la+i<=j or (j-i) in ab[0] or (i-j) in ab[1]:
            v = max([la+i,lb+j,lc]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for p in [0,1]:
 for i in ab[p]:
    i = ii if p==0 else -ii
    v = max(la,lb+i)+max(0,-i)+lc
    mn = min(mn,v)
ddprint(mn)
for p in [0,1]:
 for i in ac[p]:
    i = ii if p==0 else -ii
    v = max(la,lc+i)+max(0,-i)+lb
    mn = min(mn,v)
ddprint(mn)
for p in [0,1]:
 for i in bc[p]:
    i = ii if p==0 else -ii
    v = max(lb,lc+i)+max(0,-i)+la
    mn = min(mn,v)
print(mn)