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: Wrong Answer

Solution code:
import itertools
isdebug=0
if isdebug==0:
    s=[input(),input(),input()]
else:
    import random
    X=[chr(i+97) for i in range(26)]+["?"]
    N=2000
    s=["","",""]
    for i in range(N):
        if False:
            s[0]+=random.choice(X)
            s[1]+=random.choice(X)
            s[2]+=random.choice(X)
        else:
            s[0]+="?"
            s[1]+="?"
            s[2]+="?"
LEN=[len(s[x]) for x in range(3)]
seq=[(0,1),(1,0),(2,0),(0,2),(1,2),(2,1)]
D={t:0 for t in seq}
for x,y in seq:
    i=min(LEN[x],LEN[y])
    while(i>0):
        #print(s[x][LEN[x]-i:],s[y][:i])
        flag=1
        for j in range(i):
            if s[x][LEN[x]-i+j]!=s[y][j]:
                if s[x][LEN[x]-i+j]!="?" and s[y][j]!="?":
                    flag=0
                    break
        if flag==1:
            D[(x,y)]=i
            break
        i-=1
#print(D)
ans=sum(LEN)
for perm in itertools.permutations(range(3),3):
    ans=min(ans,sum(LEN)-D[(perm[0],perm[1])]-D[(perm[1],perm[2])])
print(ans)

Submission status: Wrong Answer

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

def eq(s,t,i):

    for _s,_t in zip(s[:i],t[-1*i:]):

        if _s==_t:
            pass
        elif _s=='?' or _t=='?':
            pass
        else:
            return False
    return True

def _join(s,t,i):
    if eq(s,t,i)==False:
        return []
    else:
        prob1=t[:len(t)-i]+s
        prob2=t+s[i:]
        if prob1==prob2:
            return [prob1]
        else:
            if prob1.count('?')<prob2.count('?'):
                return [prob1]
            else:
                return [prob2]


def join(s,t):
    retval=[]
    for i in range(len(s)+1):
        retval+=_join(s,t,i)
        retval+=_join(t,s,i)
    return retval

ab=join(a,b)
ac=join(a,c)

abc=[]
for _ab in ab:
    abc+=join(_ab,c)
for _ac in ac:
    abc+=join(_ac,b)

abc=[len(i) for i in abc]
print(min(abc))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def same(a,b,l):
        res=a[:l]
        w=0
        for c0,c1 in zip(a[l:],b):
            if c0!="?" and c1!="?" and c0!=c1:
                return "NO"
            w+=1
            if c0!="?":res+=c0
            elif c1!="?":res+=c1
            else:res+="?"
        return res+b[w:]

    ss=[SI() for _ in range(3)]
    ans=len(ss[0])+len(ss[1])+len(ss[2])
    for i in range(3):
        for j in range(3):
            if i==j:continue
            a,b=ss[i],ss[j]
            c = ss[3 - i - j]
            for l in range(len(a)):
                ret=same(a,b,l)
                if ret!="NO":
                    ab=ret
                    for ll in range(len(ab)):
                        ret = same(ab, c, ll)
                        if ret != "NO":
                            ans = min(ans, len(ret))
            ab = a+b
            for ll in range(len(ab)):
                ret = same(ab, c, ll)
                if ret != "NO":
                    #print(ret)
                    ans = min(ans, len(ret))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
K = 4000
A = input()
B = input()
C = input()
la, lb, lc = len(A), len(B), len(C)

def check(S, T):
    R = [1] * (K * 2 + 1)
    for i in range(-len(T), len(S)):
        for j in range(max(i, 0), min(len(S), len(T)+i)):
            if S[j] != T[j-i] and S[j] != "?" and T[j-i] != "?":
                R[i] = 0
                break
    return R

AB = check(A, B)
AC = check(A, C)
BC = check(B, C)

mi = K * 3
for i_ab in range(-K, K + 1):
    if AB[i_ab] == 0: continue
    for i_ac in range(max(-K, i_ab - lc), min(K + 1, i_ab + lb)):
        if AC[i_ac] == 0: continue
        if BC[i_ac - i_ab] == 0: continue
        mi = min(mi, max(i_ab + lb, i_ac + lc, la) - min(i_ab, i_ac, 0))

print(mi)

Submission status: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    z=a+['?']*zn
    r=len(a)
    k=KMP(b).search(z)[0]
    for i in range(len(b)):
        if b[i]!='?':
            z[k+i]=b[i]
    r=max(r,k+len(b))
    k=KMP(c).search(z)[0]  
    return max(r,k+len(c))
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Wrong Answer

Solution code:

a = input()
b = input()
c = input()
ans = 10**6

def e(s, t):
    ls = len(s)
    lt = len(t)
    ans = 10**6
    anss0 = []
    for i in range(ls):
        ng = 0
        anss = []
        jj = 0
        for j in range(min(len(s)-i, len(t))):
            if s[i+j] != "?" and t[j] != "?" and\
                s[i+j] != t[j]:
                ng = 1
                break
            else:
                anss.append(s[i+j] if t[j]=="?" else t[j])
            jj = j
        jj += 1
        # print(anss)
        anss = list(s[:i]) + anss
        j = jj
        if len(s)-i != len(t):
            if j < len(s)-i:
                # print("t",i,j)
                anss += s[i+j:]
            else:
                # print("s",i,j)
                anss += t[j:]
        if ng==0 and len(anss) < ans:
            ans = len(anss)
            anss0 = anss[:]
    if ans==10**6:
        ans = len(s)+len(t)
        anss0 = list(s) + list(t)
    return anss0

ans = min(len(e(e(a,b),c)), len(e(e(a,c),b)), 
len(e(e(b,a),c)), len(e(e(b,c),a)), len(e(e(c,a),b)),
len(e(e(c,b),a)))
print(ans)

Submission status: Wrong Answer

Solution code:

def link(x,y): #x>=y前提

    for i in range(len(x)+1):

        flag = True
        for j in range(len(y)):

            if j+i >= len(x):
                break

            if x[j+i] != y[j] and x[j+i] != "?" and y[j] != "?":
                flag = False
                break

        if flag:
            #print (i)
            ret = []
            for j in range(max(len(x) , len(y)+i )):

                ret.append("?")
                if j < len(x):
                    ret[-1] = max(ret[-1] , x[j])
                if i <= j and j < i+len(y):
                    ret[-1] = max(ret[-1] , y[j-i])

            return ret


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

ans = float("inf")

ans = min( len(link(link(a,b),c)) , len(link(link(a,c),b)) , len(link(link(b,a),c)) , len(link(link(b,c),a)) , len(link(link(c,a),b)) , len(link(link(c,b),a)))

print (ans)

Submission status: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    z=a+['?']*zn
    r=len(a)
    k=KMP(b).search(z)[0]
    z[k:k+len(b)]=b
    r=max(r,k+len(b))
    k=KMP(c).search(z)[0]
    
    return max(r,k+len(c))
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Wrong Answer

Solution code:
def constructable(str1,str2):
    if str1=='?' or str2=='?':
        return True
    elif str1==str2:
        return True
    else:
        return False

def condition(num):
    flag=1
    N=num
    if N<max(len(a),len(b),len(c)):
        return False

    S=[0 for i in range(0,N)]
    for i in range(0,len(a)):
        S[i]=a[i]
    for i in range(0,len(c)):
        if S[-i-1]==0:
            S[-i-1]=c[-i-1]
        else:
            if not constructable(S[-i-1],c[-i-1]):
                break
    for i in range(0,N-len(b)+1):
        start=i
        for j in range(0,len(b)):
            if  S[start+j]!=0 and not constructable(b[j],S[start+j]):
                break
        else:
            return True

    S=[0 for i in range(0,N)]
    for i in range(0,len(a)):
        S[i]=a[i]
    for i in range(0,len(b)):
        if S[-i-1]==0:
            S[-i-1]=b[-i-1]
        else:
            if not constructable(S[-i-1],b[-i-1]):
                break
    for i in range(0,N-len(c)+1):
        start=i
        for j in range(0,len(c)):
            if S[start+j]!=0 and  not constructable(c[j],S[start+j]):
                break
        else:
            return True

    S=[0 for i in range(0,N)]
    for i in range(0,len(b)):
        S[i]=b[i]
    for i in range(0,len(a)):
        if S[-i-1]==0:
            S[-i-1]=a[-i-1]
        else:
            if not constructable(S[-i-1],a[-i-1]):
                break
    for i in range(0,N-len(c)+1):
        start=i
        for j in range(0,len(c)):
            if S[start+j]!=0 and  not constructable(c[j],S[start+j]):
                break
        else:
            return True

    S=[0 for i in range(0,N)]
    for i in range(0,len(b)):
        S[i]=b[i]
    for i in range(0,len(c)):
        if S[-i-1]==0:
            S[-i-1]=c[-i-1]
        else:
            if not constructable(S[-i-1],c[-i-1]):
                break
    for i in range(0,N-len(a)+1):
        start=i
        for j in range(0,len(a)):
            if S[start+j]!=0 and not constructable(a[j],S[start+j]):
                break
        else:
            return True

    S=[0 for i in range(0,N)]
    for i in range(0,len(c)):
        S[i]=c[i]
    for i in range(0,len(a)):
        if S[-i-1]==0:
            S[-i-1]=a[-i-1]
        else:
            if not constructable(S[-i-1],a[-i-1]):
                break
    for i in range(0,N-len(b)+1):
        start=i
        for j in range(0,len(b)):
            if S[start+j]!=0 and  not constructable(b[j],S[start+j]):
                break
        else:
            return True

    S=[0 for i in range(0,N)]
    for i in range(0,len(c)):
        S[i]=c[i]
    for i in range(0,len(b)):
        if S[-i-1]==0:
            S[-i-1]=b[-i-1]
        else:
            if not constructable(S[-i-1],b[-i-1]):
                break
    for i in range(0,N-len(a)+1):
        start=i
        for j in range(0,len(a)):
            if S[start+j]!=0 and not constructable(a[j],S[start+j]):
                break
        else:
            return True

a=input()
b=input()
c=input()
s=1
e=6000
while e-s>1:
    test=(e+s)//2
    if condition(test):
        e=test
    else:
        s=test

if condition(s):
    print(s)
else:
    print(e)

Submission status: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    z=a+['?']*zn
    k=KMP(b).search(z)[0]
    z[k:k+len(b)]=b
    k=KMP(c).search(z)[0]
    return k+len(c)
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = [input() for i in range(3)]
    ans = float("inf")
    for p in permutations(range(3)):
        a,b,c = s[p[0]],s[p[1]],s[p[2]]
        k = len(a)
        p = len(a)
        for i in range(len(a)):
            for j in range(min(len(b),len(a)-i)):
                if a[i+j] != b[j] and a[i+j] != "?" and b[j] != "?":
                    break
            else:
                nk = i+len(b)
                p = i
                if k < nk:
                    k = nk
                break
        else:
            k += len(b)
        a,b = b,c
        for i in range(len(a)):
            for j in range(min(len(b),len(a)-i)):
                if a[i+j] != b[j] and a[i+j] != "?" and b[j] != "?":
                    break
            else:
                nk = p+i+len(b)
                if k < nk:
                    k = nk
                break
        else:
            k += len(b)
        if k < ans:
            ans = k
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def main():
    C = [ input() for _ in range(3)]
    LC = [ len(c) for c in C]
    ans = sum(LC)
    for P in permutations( range(3)):
        now = sum(LC)
        a, b, c = P[0], P[1], P[2]
        x, y, z = LC[a], LC[b], LC[c]
        for i in range(x):
            if x - i > y:
                continue
            check = True
            for j in range(i, x):
                if C[a][j] == '?' or C[b][j-i] == '?' or C[a][j] == C[b][j-i]:
                    continue
                check = False
                break
            if check:
                now -= x-i
                break
        for i in range(y):
            if y - i > z:
                continue
            check = True
            for j in range(i, y):
                if C[b][j] == '?' or C[c][j-i] == '?' or C[b][j] == C[c][j-i]:
                    continue
                check = False
                break
            if check:
                now -= y-i
                break
        if now < ans:
            ans = now
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a = 'a'*2000
b = 'b'*2000
c = 'c'*2000

len_a = len(a)
len_b = len(b)
len_c = len(c)

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

dp_len=50000
ab = [True] * dp_len
ac = [True] * dp_len
bc = [True] * dp_len

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+dp_len//2] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

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

ans = len_max
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+dp_len//2] and ac[j+dp_len//2] and bc[j-i+dp_len//2]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]

len_a = len(a)
len_b = len(b)
len_c = len(c)

a += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
c += [63] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)

for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False

"""
# AC
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
"""
# TLE?
candidates = []
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            candidates.append(max(len_a, len_b + len1, len_c + len1 + len2))
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            candidates.append(max(len_b, len_a + len1, len_c + len1 + len2))
        if bc[len1] and ca[len2] and ba[len1 + len2]:
            candidates.append(max(len_b, len_c + len1, len_a + len1 + len2))
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            candidates.append(max(len_c, len_b + len1, len_a + len1 + len2))
        if ca[len1] and ab[len2] and cb[len1 + len2]:
            candidates.append(max(len_c, len_a + len1, len_b + len1 + len2))
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            candidates.append(max(len_a, len_c + len1, len_b + len1 + len2))
print(min(candidates))

Submission status: Time Limit Exceeded

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]

len_a = len(a)
len_b = len(b)
len_c = len(c)

a += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
c += [63] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)

for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False

ans = MAX_N * 6
# TLE?
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        length = len1 + len2
        if ab[len1] and bc[len2] and ac[length]:
            tmp = max(len_a, len_b + len1, len_c + length)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[length]:
            tmp = max(len_b, len_a + len1, len_c + length)
            ans = min(ans, tmp)
        if bc[len1] and ca[len2] and ba[length]:
            tmp = max(len_b, len_c + len1, len_a + length)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[length]:
            tmp = max(len_c, len_b + len1, len_a + length)
            ans = min(ans, tmp)
        if ca[len1] and ab[len2] and cb[length]:
            tmp = max(len_c, len_a + len1, len_b + length)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[length]:
            tmp = max(len_a, len_c + len1, len_b + length)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""


def main():
    MAX_N = 2000
    a = [ord(char) for char in input()]
    b = [ord(char) for char in input()]
    c = [ord(char) for char in input()]

    len_a = len(a)
    len_b = len(b)
    len_c = len(c)

    a += [63] * (MAX_N - len_a + 10)
    b += [63] * (MAX_N - len_b + 10)
    c += [63] * (MAX_N - len_c + 10)

    ab = [True] * (2 * MAX_N + 10)
    ba = [True] * (2 * MAX_N + 10)
    bc = [True] * (2 * MAX_N + 10)
    cb = [True] * (2 * MAX_N + 10)
    ca = [True] * (2 * MAX_N + 10)
    ac = [True] * (2 * MAX_N + 10)

    for length in range(MAX_N + 1):
        for i in range(MAX_N + 1):
            if i + length > MAX_N:
                break

            if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
                ab[length] = False
            if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
                ba[length] = False

            if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
                bc[length] = False
            if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
                cb[length] = False

            if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
                ca[length] = False
            if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
                ac[length] = False

    ans = MAX_N * 6
    """
    # AC
    for len1 in range(MAX_N + 1):
        for len2 in range(MAX_N + 1):
            if ab[len1] and bc[len2] and ac[len1 + len2]:
                tmp = max(len_a, len_b + len1, len_c + len1 + len2)
                ans = min(ans, tmp)
            if ba[len1] and ac[len2] and bc[len1 + len2]:
                tmp = max(len_b, len_a + len1, len_c + len1 + len2)
                ans = min(ans, tmp)

    for len1 in range(MAX_N + 1):
        for len2 in range(MAX_N + 1):
            if bc[len1] and ca[len2] and ba[len1 + len2]:
                tmp = max(len_b, len_c + len1, len_a + len1 + len2)
                ans = min(ans, tmp)
            if cb[len1] and ba[len2] and ca[len1 + len2]:
                tmp = max(len_c, len_b + len1, len_a + len1 + len2)
                ans = min(ans, tmp)

    for len1 in range(MAX_N + 1):
        for len2 in range(MAX_N + 1):
            if ca[len1] and ab[len2] and cb[len1 + len2]:
                tmp = max(len_c, len_a + len1, len_b + len1 + len2)
                ans = min(ans, tmp)
            if ac[len1] and cb[len2] and ab[len1 + len2]:
                tmp = max(len_a, len_c + len1, len_b + len1 + len2)
                ans = min(ans, tmp)
    """
    # TLE?
    for len1 in range(MAX_N + 1):
        for len2 in range(MAX_N + 1):
            if ab[len1] and bc[len2] and ac[len1 + len2]:
                tmp = max(len_a, len_b + len1, len_c + len1 + len2)
                ans = min(ans, tmp)
            if ba[len1] and ac[len2] and bc[len1 + len2]:
                tmp = max(len_b, len_a + len1, len_c + len1 + len2)
                ans = min(ans, tmp)

            if bc[len1] and ca[len2] and ba[len1 + len2]:
                tmp = max(len_b, len_c + len1, len_a + len1 + len2)
                ans = min(ans, tmp)
            if cb[len1] and ba[len2] and ca[len1 + len2]:
                tmp = max(len_c, len_b + len1, len_a + len1 + len2)
                ans = min(ans, tmp)

            if ca[len1] and ab[len2] and cb[len1 + len2]:
                tmp = max(len_c, len_a + len1, len_b + len1 + len2)
                ans = min(ans, tmp)
            if ac[len1] and cb[len2] and ab[len1 + len2]:
                tmp = max(len_a, len_c + len1, len_b + len1 + len2)
                ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [63] * (MAX_N - len_a + 10)
b = b + [63] * (MAX_N - len_b + 10)
c = c + [63] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False


ans = MAX_N * 6
"""
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
"""
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)