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:
a = list(input())
b = list(input())
c = list(input())

import itertools
L = [a, b, c]

ans = len(a) + len(b) + len(c)

def nasu(x, y, z, ans):
  X = len(x)
  Y = len(y)
  f = False
  for i in range(min(ans - Y, X)):
    for j in range(Y):
      if i + j >= X:
        ans = min(ans, honya(x, i, y, z, ans))
        F = True
        break
      if x[i + j] != "?" and y[j] != "?":
        if x[i + j] != y[j]:
          break
    else:
      ans = min(ans, honya(x, i,y, z, ans))
      F = True
    if f:
      break
  return ans

def honya(x, n, y, z, ans):
  k = max(len(x), n + len(y))
  X = len(x)
  Y = len(y)
  Z = len(z)
  f = False
  for i in range(min(ans - Z, k)):
    for j in range(Z):
      if i + j >= k:
        ans = min(ans, i + Z)
        f = True
        break
      if z[j] != "?":
        if i + j < X:
          if x[i + j] != "?" and x[i + j] != z[j]:
            break
        if i + j >= n and i + j < n + Y:
          if y[i + j - n] != "?" and y[i + j - n] != z[j]:
            break
    else:
      ans = min(ans, k)
      f = True
      break
    if f:
      break
  return ans

for i in itertools.permutations([0, 1, 2]):
  x = L[i[0]]
  y = L[i[1]]
  z = L[i[2]]
  ans = min(ans, nasu(x, y, z, ans))

print(ans)

Submission status: Time Limit Exceeded

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

import itertools
L = [a, b, c]

ans = len(a) + len(b) + len(c)

def nasu(x, y, z, ans):
  X = len(x)
  Y = len(y)
  f = False
  for i in range(min(ans - Y, X)):
    for j in range(Y):
      if i + j >= X:
        ans = min(ans, honya(x, i, y, z, ans))
        F = True
        break
      if x[i + j] != "?" and y[j] != "?":
        if x[i + j] != y[j]:
          break
    else:
      ans = min(ans, honya(x, i,y, z, ans))
      F = True
    if f:
      break
  return ans

def honya(x, n, y, z, ans):
  k = max(len(x), n + len(y))
  X = len(x)
  Y = len(y)
  Z = len(z)
  for i in range(min(ans - Z, k)):
    for j in range(Z):
      if i + j >= k:
        ans = min(ans, i + Z)
        break
      if z[j] != "?":
        if i + j < X:
          if x[i + j] != "?" and x[i + j] != z[j]:
            break
        if i + j >= n and i + j < n + Y:
          if y[i + j - n] != "?" and y[i + j - n] != z[j]:
            break
    else:
      ans = min(ans, k)
      break
  return ans

for i in itertools.permutations([0, 1, 2]):
  x = L[i[0]]
  y = L[i[1]]
  z = L[i[2]]
  ans = min(ans, nasu(x, y, z, ans))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = [input(),input(),input()]
l = [len(a[0]),len(a[1]),len(a[2])]
ans = l[0]+l[1]+l[2]

def check(a0, l0, a1, l1, delta):
    # stt1 >= stt0, stt1 - stt0 >=l0 must return True
    i = delta
    j = 0
    while (i<l0) and (j<l1):
        if a0[i] != a1[j]:
            if a0[i] != '?' and a1[j] != '?':
                return False
        i += 1
        j += 1
    return True

memoLen = ans-min(l[0],l[1],l[2])+1
memo = [[[1]*memoLen for i in range(3)] for j in range(3)]
comb2 = [(0,1),(1,0),(1,2),(2,1),(0,2),(2,0)]
for x, y in comb2:
    me = memo[x][y]
    a0, a1 = a[x],a[y]
    l0, l1 = l[x],l[y]
    for delta in range(0,l0):
        if not check(a0,l0, a1,l1, delta):
            me[delta] = 0

comb = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]
for i,j,k in comb:
    l0, l1, l2 = l[i],l[j],l[k]
    for stt1 in range(0,l0+1):
        if memo[i][j][stt1]:
            l01 = max(l0,stt1+l1)
            for stt2 in range(stt1,l01+1):
                if memo[j][k][stt2-stt1] and memo[i][k][stt2]:
                    l012 = max(l01,stt2+l2)
                    ans = min(ans,l012)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

a = [input(),input(),input()]
l = [len(a[0]),len(a[1]),len(a[2])]
full = l[0]+l[1]+l[2]
b = ['?']*full

def permList(s):
    p = []
    l = len(s)
    if not l:
        return [[]]
    for i in range(l):
        for post in permList(s[:i]+s[i+1:]):
            p.append([s[i]]+post)
    return p
comb = permList([0,1,2])

def check(stt0, a0, l0, stt1, a1, l1):
    i = stt1 - stt0
    j = 0
    while i<l0 and j<l1:
        if a0[i] != a1[j]:
            if a0[i] != '?' and a1[j] != '?':
                return False
        i += 1
        j += 1
    return True

ans = l[0]+l[1]+l[2]
for i,j,k in comb:
    a0, a1, a2 = a[i],a[j],a[k]
    l0, l1, l2 = l[i],l[j],l[k]
    stt0 = 0
    for stt1 in range(0,l0+1):
        if not check(stt0,a0,l0, stt1,a1,l1):
            continue
        l01 = max(l0,stt1+l1)
        for stt2 in range(stt1,l01+1):
            if not check(stt1,a1,l1, stt2,a2,l2):
                continue
            if not check(stt0,a0,l0, stt2,a2,l2):
                continue
            l012 = max(l01,stt2+l2)
            ans = min(ans,l012)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
a = input()
b = input()
c = input()
s = 0
A = len(a)
B = len(b)
C = len(c)
#ab,ac,bcに対して相対位置を-2000~2000までずらした時に矛盾が生じないかどうかを前計算する
ab =[True]*20000
ac = [True]*20000
bc = [True] * 20000

#定数倍高速化を試みる
def match(s1,s2,ss):
    len2 =len(s2)
    len1 = len(s1)
    for i in range(-2000,2001):
        #文字列s1の左端を0として、s2の左端がiに存在する
        for j in range(0,len2):
            if i+j < 0: continue
            if i+j >= len1: continue
            if s2[j] == "?" or s1[i+j] == "?" or s2[j] == s1[i+j]:
                continue
            else:
                ss[i+10000] = False
                break
match(a,b,ab)
match(a,c,ac)
match(b,c,bc)

ans = 6000
# aの左端を０とした時に、b,cの位置をi,jとして全探索する
for i in range(-4000,4000):
    for j in range(-4000,4000):
        if ab[i+10000] and ac[j+10000] and bc[j-i+10000]:
            #矛盾がないパターンなのでansを更新
            left = min(0,min(i,j))
            right = max(A,max(B+i,C+j))
            ans = min(ans,right- left)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
a = input()
b = input()
c = input()
s = 0
#ab,ac,bcに対して相対位置を-2000~2000までずらした時に矛盾が生じないかどうかを前計算する
ab =[True]*20000
ac = [True]*20000
bc = [True] * 20000

def match(s1,s2,ss):
    for i in range(-2000,2001):
        #文字列s1の左端を0として、s2の左端がiに存在する
        for j in range(len(s2)):
            if i+j < 0: continue
            if i+j >= len(s1): continue
            if s2[j] == "?" or s1[i+j] == "?" or s2[j] == s1[i+j]:
                continue
            else:
                ss[i+10000] = False
                break
match(a,b,ab)
match(a,c,ac)
match(b,c,bc)

ans = 6000
# aの左端を０とした時に、b,cの位置をi,jとして全探索する
for i in range(-4000,4000):
    for j in range(-4000,4000):
        if ab[i+10000] and ac[j+10000] and bc[j-i+10000]:
            #矛盾がないパターンなのでansを更新
            left = min(0,min(i,j))
            right = max(len(a),max(len(b)+i,len(c)+j))
            ans = min(ans,right- left)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
a = input()
b = input()
c = input()
s = 0
#ab,ac,bcに対して相対位置を-2000~2000までずらした時に矛盾が生じないかどうかを前計算する
ab =[True]*20000
ac = [True]*20000
bc = [True] * 20000

def match(s1,s2,ss):
    for i in range(-2000,2001):
        #文字列s1の左端を0として、s2の左端がiに存在する
        for j in range(len(s2)):
            if i+j < 0: continue
            if i+j >= len(s1): continue
            if s2[j] == s1[i+j] or s2[j] == "?" or s1[i+j] == "?":
                continue
            else:
                ss[i+10000] = False
                break
match(a,b,ab)
match(a,c,ac)
match(b,c,bc)

ans = 6000
# aの左端を０とした時に、b,cの位置をi,jとして全探索する
for i in range(-4000,4000):
    for j in range(-4000,4000):
        if ab[i+10000] and ac[j+10000] and bc[j-i+10000]:
            #矛盾がないパターンなのでansを更新
            left = min(0,min(i,j))
            right = max(len(a),max(len(b)+i,len(c)+j))
            ans = min(ans,right- left)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def match(ch1, ch2):
    return ch1 == ch2 or ch1 == '?' or ch2 == '?'

def solve():
    MAXLEN = 2000
    a = raw_input()
    b = raw_input()
    c = raw_input()
    lA = len(a); lB = len(b); lC = len(c)
    MAXLEN = max(lA, lB, lC)
    ab = [True for i in range(10*MAXLEN)]
    ac = [True for i in range(10*MAXLEN)]
    bc = [True for i in range(10*MAXLEN)]
    for i in range(lA):
        for j in range(lB):
            if not match(a[i], b[j]):
                ab[i - j + 5 * MAXLEN] = False
    for i in range(lA):
        for j in range(lC):
            if not match(a[i], c[j]):
                ac[i - j + 5 * MAXLEN] = False
    for i in range(lB):
        for j in range(lC):
            if not match(b[i], c[j]):
                bc[i - j + 5 * MAXLEN] = False
    ret = lA + lB + lC
    for i in range(-2*MAXLEN, 2*MAXLEN+1):
        for j in range(-2*MAXLEN, 2*MAXLEN+1):
            if ab[i + 5*MAXLEN] and ac[j + 5*MAXLEN] and bc[j - i + 5*MAXLEN]:
                L = min(0, i, j)
                R = max(lA, lB + i, lC + j)
                ret = min(ret, R - L)
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
MAXLEN = 2000

def match(ch1, ch2):
    return ch1 == ch2 or ch1 == '?' or ch2 == '?'

def solve():
    a = raw_input()
    b = raw_input()
    c = raw_input()
    lA = len(a); lB = len(b); lC = len(c)
    ab = [True for i in range(10*MAXLEN)]
    ac = [True for i in range(10*MAXLEN)]
    bc = [True for i in range(10*MAXLEN)]
    for i in range(lA):
        for j in range(lB):
            if not match(a[i], b[j]):
                ab[i - j + 5 * MAXLEN] = False
    for i in range(lA):
        for j in range(lC):
            if not match(a[i], c[j]):
                ac[i - j + 5 * MAXLEN] = False
    for i in range(lB):
        for j in range(lC):
            if not match(b[i], c[j]):
                bc[i - j + 5 * MAXLEN] = False
    ret = lA + lB + lC
    for i in range(-2*MAXLEN, 2*MAXLEN+1):
        for j in range(-2*MAXLEN, 2*MAXLEN+1):
            if ab[i + 5*MAXLEN] and ac[j + 5*MAXLEN] and bc[j - i + 5*MAXLEN]:
                L = min(0, i, j)
                R = max(lA, lB + i, lC + j)
                ret = min(ret, R - L)
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

M = 2000
a = input().rstrip()
b = input().rstrip()
c = input().rstrip()
A = len(a)
B = len(b)
C = len(c)

ab = [False] * 20000
ac = [False] * 20000
bc = [False] * 20000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i - j + 10000] = True
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i - j + 10000] = True
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i - j + 10000] = True

ans = 3 * M
for i in range(-2 * M, 2 * M + 1):
    for j in range(-2 * M, 2 * M + 1):
        if not ab[i + 10000] and not ac[j + 10000] and not bc[j - i + 10000]:
            print("match", i, j)
            l = min(0, min(i, j))
            r = max(A, min(B + i, C + j))
            ans = min(ans, r - l)
            print("ans", ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import permutations

A = input()
B = input()
C = input()

ans = len(A) + len(B) + len(C)

def merge(X, Y, max_len, offset=None):
  ret = deque()
  for i in range(offset or 0, min(len(X), max_len - len(Y))):
    s = deque(X[:i])
    for x, y in zip(X[i:], Y):
      if x == '?' or x == y:
        s.append(y)
      elif y == '?':
        s.append(x)
      else:
        break
    else:
      s.extend(X[i+len(Y):])
      s.extend(Y[len(X)-i:])
      ret.append((list(s), i))
      if offset != None:
        break
  return ret

for X, Y, Z in permutations([A, B, C]):
  for W, i in merge(X, Y, ans):
    ans = min(ans, len(W) + len(Z))
    for V, _ in merge(W, Z, ans, i):
      ans = min(ans, len(V))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
A = input()
B = input()
C = input()
N = max(len(A), len(B), len(C)) * 2

S = ('?' * N) + A + ('?' * N)

def isOkA(left, T):
    for s, t in zip(S[left:], T):
        if s == '?' or t == '?':
            continue
        if s != t:
            return False
    return True

def isOkBC(leftB, leftC):
    I = set(range(leftB, leftB + len(B)))
    J = set(range(leftC, leftC + len(C)))

    for k in (I & J):
        i = k - leftB
        j = k - leftC
        if B[i] == '?' or C[j] == '?':
            continue
        if B[i] != C[j]:
            return False
    return True

leftB = [i for i in range(len(S) - len(B)) if isOkA(i, B)]
leftC = [i for i in range(len(S) - len(C)) if isOkA(i, C)]

ans = len(A) + len(B) + len(C)
for i in leftB:
    for j in leftC:
        if isOkBC(i, j):
            length = max(N + len(A), i + len(B), j + len(C)) - min(i, j, N)
            ans = min(ans, length)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

A = input()
B = input()
C = input()
N = max(len(A), len(B), len(C)) * 2

S = ('?' * N) + A + ('?' * N)

def isOk(leftB, leftC):
    T = defaultdict(lambda : '?')

    for (i, s), b in zip(enumerate(S[leftB:], start=leftB), B):
        if b == '?':
            continue
        if s == '?':
            T[i] = b
            continue
        if s != b:
            return False

    for (i, s), c in zip(enumerate(S[leftC:], start=leftC), C):
        if c == '?':
            continue
        if s == '?' and (i in T and T[i] != c):
            return False
        if s == '?':
            continue
        if s != c:
            return False

    return True

ans = len(A) + len(B) + len(C)

for i in range(len(S) - len(B)):
    for j in range(len(S) - len(C)):
        if isOk(i, j):
            length = max(N + len(A), i + len(B), j + len(C)) - min(i, j, N)
            ans = min(ans, length)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def get_keys_from_value(d, val):
    return [k for k,v in d.items() if v == val]

s = {}
a = list(input())
b = list(input())
c = list(input())
L_a,L_b, L_c = len(a),len(b),len(c)

alllength = L_a + L_b + L_c

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

ab,bc,ac = dict(),{},{}
for i in range(-L_c - L_b, L_a + L_c):
    ab[i] = True
for i in range(-L_a - L_c , L_b + L_c):
    bc[i] = True
for i in range(-L_c-L_b, L_a +L_b):
    ac[i] = True
for i in range(L_a):
    for j in range(L_b):
        ab[i-j] &=match(a[i],b[j])

for i in range(L_b):
    for j in range(L_c):
        bc[i-j] &= match(b[i],c[j])

for i in range(L_a):
    for j in range(L_c):
        ac[i-j] &= match(a[i],c[j])

min_len = 10000
T_ab = get_keys_from_value(ab,True)
T_bc = get_keys_from_value(bc,True)

for x in T_ab:
    for y in T_bc:
        if x+y >= -L_c-L_b and x+y < L_a +L_b:
            if ac[x+y] == True:
                d = min(0,x,x+y)
                e = max(len(a),len(b)+x,len(c)+x+y)
                if min_len > e -d:
                    min_len = e - d

print(min_len)

Submission status: Time Limit Exceeded

Solution code:
a, b, c = (input() for _ in range(3))
A, B, C = (len(x) for x in (a, b, c))
ans = A + B + C

for i in range(-B - C, B + C + 1):
    for j in range(-B - C, B + C + 1):
        l = min(0, i, j)
        r = max(A, B + i, C + j)
        if r - l >= ans:
            continue
        for k in range(l, r):
            char_set = set()
            if 0 <= k < A:
                char_set.add(a[k])
            if i <= k < i + B:
                char_set.add(b[k - i])
            if j <= k < j + C:
                char_set.add(c[k - j])
            char_set.discard("?")
            if len(char_set) > 1:
                break
        else:
            ans = min(ans, r - l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def isValid(A, B):
    return all(a == "?" or b == "?" or a == b for a, b in zip(A, B))


def Valid2Str(A, B):
    if len(A) < len(B):
        A, B = B, A

    for i in range(len(B) + 1):
        if isValid(A[:i], B[len(B) - i:]):
            yield B + A[i:]
    for i in range(len(A) - len(B)):
        if isValid(A[i + 1:i + 1 + len(B)], B):
            yield A
            break
    for i in range(len(B)):
        if isValid(A[len(A) - i:], B[:i]):
            yield A + B[i:]


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

ans = len(a) + len(b) + len(c)

for s in Valid2Str(a, b):
    for t in Valid2Str(s, c):
        ans = min(ans, len(t))

for s in Valid2Str(b, c):
    for t in Valid2Str(s, a):
        ans = min(ans, len(t))

for s in Valid2Str(c, a):
    for t in Valid2Str(s, b):
        ans = min(ans, len(t))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

def concat1(x,y,len_only=False):
    n = len(x)
    m = len(y)
    ret = [x+y]
    for i in range(n):
        con_flag = False
        d = {}
        for j in range(i,min(i+m,n)):
            if x[j] == '?' and y[j-i] != '?':
                d[j] = y[j-i]
            elif x[j] != y[j-i] and x[j] != '?' and y[j-i] != '?':
                con_flag = True
                break
            else:
                continue
        if con_flag:
            continue
        else:
            if len_only:
                if n-i <= m-1:
                    return m+i
                else:
                    return n
            else:
                if n-i <= m-1:
                    now = x+y[n-i:]
                    for k,v in d.items():
                        now[k] = v
                else:
                    now = x[:]
                    for k,v in d.items():
                        now[k] = v
                ret.append(now)

    if len_only:
        return n+m
    else:
        return ret

def concat2(xlist,y):
    ans = float('inf')
    for x in xlist:
        now = concat1(x,y,len_only=True)
        min_ = now
        if min_ < ans:
            ans = min_
    return ans


ret1 = concat2(concat1(a,b),c)
ret2 = concat2(concat1(a,c),b)
ret3 = concat2(concat1(b,a),c)
ret4 = concat2(concat1(b,c),a)
ret5 = concat2(concat1(c,a),b)
ret6 = concat2(concat1(c,b),a)

print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

def concat1(x,y,len_only=False):
    n = len(x)
    m = len(y)
    if len_only:
        ret = [n+m]
    else:
        ret = [x+y]
    for i in range(n):
        con_flag = False
        d = {}
        for j in range(i,min(i+m,n)):
            if x[j] == '?' and y[j-i] != '?':
                d[j] = y[j-i]
            elif x[j] != y[j-i] and x[j] != '?' and y[j-i] != '?':
                con_flag = True
                break
            else:
                continue
        if con_flag:
            continue
        else:
            if len_only:
                if n-i <= m-1:
                    ret.append(m+i)
                else:
                    ret.append(n)
            else:
                if n-i <= m-1:
                    now = x+y[n-i:]
                    for k,v in d.items():
                        now[k] = v
                else:
                    now = x
                    for k,v in d.items():
                        now[k] = v
                ret.append(now)

    return ret

def concat2(xlist,y):
    ans = float('inf')
    for x in xlist:
        now = concat1(x,y,len_only=True)
        min_ = min(now)
        if min_ < ans:
            ans = min_
    return ans


ret1 = concat2(concat1(a,b),c)
ret2 = concat2(concat1(a,c),b)
ret3 = concat2(concat1(b,a),c)
ret4 = concat2(concat1(b,c),a)
ret5 = concat2(concat1(c,a),b)
ret6 = concat2(concat1(c,b),a)

print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

def concat1(x,y,len_only=False):
    ret = []
    n = len(x)
    m = len(y)
    for i in range(n):
        con_flag = False
        d = {}
        for j in range(i,min(i+m,n)):
            if x[j] == '?' and y[j-i] != '?':
                d[j] = y[j-i]
            elif x[j] != y[j-i] and x[j] != '?' and y[j-i] != '?':
                con_flag = True
                break
            else:
                continue
        if con_flag:
            continue
        else:
            if n-i <= m-1:
                now = x+y[n-i:]
                for k,v in d.items():
                    now[k] = v
            else:
                now = x
                for k,v in d.items():
                    now[k] = v
            if len_only:
                ret.append(len(now))
            else:
                ret.append(now)
    if len_only:
        ret.append(n+m)
    else:
        ret.append(x+y)               
    return ret

def concat2(xlist,y):
    ans = float('inf')
    for x in xlist:
        now = concat1(x,y,len_only=True)
        min_ = min(now)
        if min_ < ans:
            ans = min_
    return ans


ret1 = concat2(concat1(a,b),c)
ret2 = concat2(concat1(a,c),b)
ret3 = concat2(concat1(b,a),c)
ret4 = concat2(concat1(b,c),a)
ret5 = concat2(concat1(c,a),b)
ret6 = concat2(concat1(c,b),a)

print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Submission status: Time Limit Exceeded

Solution code:
a, b, c = [list(map(lambda x: ord(x) , list(str(input().rstrip())))) for _ in range(3)]
M = 2000
base = M * 5
ab, ac, bc = [[False for _ in range(base*2)] for _ in range(3)]
q = ord('?')
def match_chr(c1, c2):
    return c1 == q or c2 == q or c1 == c2

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

for i in range(A):
    for j in range(B):
        if not match_chr(a[i], b[j]):
            ab[i-j+base] = True
    for j in range(C):
        if not match_chr(a[i], c[j]):
            ac[i-j+base] = True
for i in range(B):
    for j in range(C):
        if not match_chr(b[i], c[j]):
            bc[i-j+base] = True

ans = 3 * M
for i in range(-2*M, 2*M+1):
    for j in range(-2*M, 2*M+1):
        if not ab[i+base] and not ac[j+base] and not bc[j-i+base]:
            l = min(0, min(i, j))
            r = max(A, max(B+i, C+j))
            ans = min(ans, r-l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b, c = [list(str(input().rstrip())) for _ in range(3)]
M = 2000
base = M * 5
ab, ac, bc = [[False for _ in range(base*2)] for _ in range(3)]

def match_chr(c1, c2):
    return c1 == '?' or c2 == '?' or c1 == c2

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

for i in range(A):
    for j in range(B):
        if not match_chr(a[i], b[j]):
            ab[i-j+base] = True
for i in range(A):
    for j in range(C):
        if not match_chr(a[i], c[j]):
            ac[i-j+base] = True
for i in range(B):
    for j in range(C):
        if not match_chr(b[i], c[j]):
            bc[i-j+base] = True

ans = 3 * M
for i in range(-2*M, 2*M+1):
    for j in range(-2*M, 2*M+1):
        if not ab[i+base] and not ac[j+base] and not bc[j-i+base]:
            l = min(0, min(i, j))
            r = max(A, max(B+i, C+j))
            ans = min(ans, r-l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/panasonic2020/submissions/10891808
# generatorを使うところ

def solve_panasonic2020_e():
    A = input()
    B = input()
    C = input()

    MX = max(map(len, [A, B, C]))

    def matching_list(P: str, Q: str, MX: int = MX) -> list:
        """相対位置ごとの文字列マッチングの可否を調べる
        ret[index差]:=その相対位置でマッチしないときTrue
        [-MX,MX]
        + : 左文字より右文字が右にある, P->Q
        - : 右文字より左文字が右にある, Q->P"""

        def unmatched(c1: str, c2: str) -> bool:
            """c1,c2がマッチしない"""
            return not (c1 == '?' or c2 == '?' or c1 == c2)

        ret = [False] * (MX * 4 + 1)
        for i, p in enumerate(P):
            for j, q in enumerate(Q):
                ret[i - j] |= unmatched(p, q)
        return ret

    ab = matching_list(A, B)
    ac = matching_list(A, C)
    bc = matching_list(B, C)

    def candidates(MX: int = MX) -> int:
        """Aに対するB,Cの相対位置MX**2で全探索し
        文字列長の候補を返すgenerator"""
        for i in range(-MX * 2, MX * 2 + 1):  # ACBのようにAB間にMX分空くこともあって、幅2MX
            if ab[i]: continue
            for j in range(-MX * 2, MX * 2 + 1):  # ABCのようにAC間にMX分空くこともあって、幅2MX
                if ac[j]: continue
                if bc[j - i]: continue
                # 添え字で混乱するが
                # ab[i-j]で
                # 添え字i-jは(bの開始)-(aの開始)を意味したことから
                # (i-j>0でa->bの配置から)
                # 今回i,jは(aの開始)を基準にした(b,cの開始位置)で
                # bcの添え字は(cの開始)-(bの開始)なのでj-i

                # [L,R)
                L = min(0, i, j)
                R = max(len(A), i + len(B), j + len(C))
                yield R - L

    ans = min(candidates())
    print(ans)
    return


if __name__ == '__main__':
    solve_panasonic2020_e()

# N**3は通らない
# N**2の方針=2本の文字列の捜査

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/panasonic2020/submissions/10891808
# generatorを使うところ

def solve_panasonic2020_e():
    A = input()
    B = input()
    C = input()

    MX = max(map(len, [A, B, C]))

    def matching_list(P: str, Q: str) -> list:
        """相対位置ごとの文字列マッチングの可否を調べる
        ret[index差]:=その相対位置でマッチしないときTrue
        [-MX,MX]
        + : 左文字より右文字が右にある, P->Q
        - : 右文字より左文字が右にある, Q->P"""

        def unmatched(c1: str, c2: str) -> bool:
            """c1,c2がマッチしない"""
            return not (c1 == '?' or c2 == '?' or c1 == c2)

        ret = [False] * (MX * 4 + 1)
        for i, p in enumerate(P):
            for j, q in enumerate(Q):
                ret[i - j] |= unmatched(p, q)
        return ret

    ab = matching_list(A, B)
    ac = matching_list(A, C)
    bc = matching_list(B, C)

    def candidates() -> int:
        """Aに対するB,Cの相対位置MX**2で全探索し
        文字列長の候補を返すgenerator"""
        for i in range(-MX * 2, MX * 2 + 1):  # ACBのようにAB間にMX分空くこともあって、幅2MX
            if ab[i]: continue
            for j in range(-MX * 2, MX * 2 + 1):  # ABCのようにAC間にMX分空くこともあって、幅2MX
                if ac[j]: continue
                if bc[j - i]: continue
                # 添え字で混乱するが
                # ab[i-j]で
                # 添え字i-jは(bの開始)-(aの開始)を意味したことから
                # (i-j>0でa->bの配置から)
                # 今回i,jは(aの開始)を基準にした(b,cの開始位置)で
                # bcの添え字は(cの開始)-(bの開始)なのでj-i

                # [L,R)
                L = min(0, i, j)
                R = max(len(A), i + len(B), j + len(C))
                yield R - L

    ans = min(candidates())
    print(ans)
    return


if __name__ == '__main__':
    solve_panasonic2020_e()

# N**3は通らない
# N**2の方針=2本の文字列の捜査

Submission status: Time Limit Exceeded

Solution code:
# 解説の写経

def solve_panasonic2020_e():
    def unmatched(c1: str, c2: str) -> bool:
        """c1,c2がマッチしない"""
        return not (c1 == '?' or c2 == '?' or c1 == c2)

    A = input()
    B = input()
    C = input()

    MX = max(map(len, [A, B, C]))

    # 相対位置ごとの文字列マッチングの可否を調べる
    # ab/ac/bc[index差]:=その相対位置でマッチしないときTrue
    # [-MX,MX]
    # + : 左文字より右文字が右にある, a->b
    # - : 右文字より左文字が右にある, b->a
    ab = [False] * (MX * 4 + 1)
    ac = [False] * (MX * 4 + 1)
    bc = [False] * (MX * 4 + 1)

    for i, a in enumerate(A):
        for j, b in enumerate(B):
            ab[i - j] |= unmatched(a, b)

    for i, a in enumerate(A):
        for j, c in enumerate(C):
            ac[i - j] |= unmatched(a, c)

    for i, b in enumerate(B):
        for j, c in enumerate(C):
            bc[i - j] |= unmatched(b, c)

    # Aに対するB,Cの相対位置MX**2で全探索
    ans = sum(map(len, [A, B, C]))
    for i in range(-MX * 2, MX * 2 + 1):  # ACBのようにAB間にMX分空くこともあって、幅2MX
        if ab[i]: continue
        for j in range(-MX * 2, MX * 2 + 1):  # ABCのようにAC間にMX分空くこともあって、幅2MX
            if ac[j]: continue
            if bc[j - i]: continue
            # 添え字で混乱するが
            # ab[i-j]で
            # 添え字i-jは(bの開始)-(aの開始)を意味したことから
            # (i-j>0でa->bの配置から)
            # 今回i,jは(aの開始)を基準にした(b,cの開始位置)で
            # bcの添え字は(cの開始)-(bの開始)なのでj-i

            # [L,R)
            L = min(0, i, j)
            R = max(len(A), i + len(B), j + len(C))
            ans = min(ans, R - L)

    print(ans)
    return


if __name__ == '__main__':
    solve_panasonic2020_e()

# N**3は通らない
# N**2の方針=2本の文字列の捜査