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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a = [[c for c in S()] for _ in range(3)]
    def f(a):
        t = a[0][:]
        b = a[1]
        l = len(t)
        bi = l
        bl = len(b)
        for i in range(l):
            bf = True
            for j in range(bl):
                if i + j >= l:
                    break
                if t[i+j] != '?' and b[j] != '?' and t[i+j] != b[j]:
                    bf = False
                    break
            if bf:
                bi = i
                break
        for j in range(bl):
            if bi+j >= l:
                t += b[j:]
                break
            if t[bi+j] == '?':
                t[bi+j] = b[j]

        c = a[2]
        l = len(t)
        ci = l
        cl = len(c)
        for i in range(bi, l):
            cf = True
            for j in range(cl):
                if i + j >= l:
                    break
                if t[i+j] != '?' and c[j] != '?' and t[i+j] != c[j]:
                    cf = False
                    break
            if cf:
                ci = i
                break
        return ci + cl

    r = inf
    for aa in itertools.permutations(a, 3):
        t = f(aa)
        if r > t:
            r = t

    return r


print(main())

Submission status: Wrong Answer

Solution code:
from itertools import permutations
A = input()
B = input()
C = input()
abc = [A,B,C]
num = [0,1,2]
ans = 6000
for i,j,k in permutations(num):
    a = abc[i]
    b = abc[j]
    c = abc[k]
    for i in range(len(a)):
        flag = True
        for j in range(len(a)-i):
            if len(b) == j or not (a[i+j] == b[j] or (a[i+j] == '?' or b[j] == '?')):
                flag = False
                break
        if flag:
            ab = a +b[j+1:]
            break
    if not flag:
        ab = a+b
    for i in range(len(ab)):
        flag = True
        for j in range(len(ab)-i):
            if len(c) == j or not (ab[i+j] == c[j] or (ab[i+j] == '?' or c[j] == '?')):
                flag = False
                break
        if flag:
            abc1 = ab +c[j+1:]
            break
    if not flag:
        abc1 = ab+c
    ans = min(ans,len(abc1))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


class Solution:

    def solve(self, a: str, b: str, c: str) -> int:

        m = {}
        for x, y in itertools.permutations([a, b, c], 2):
            if not (x, y) in m:
                li = []
                for i in range(len(x) + 1):
                    tf = True
                    for j in range(i, min(len(x), i + len(y))):
                        if x[j] != '?' and y[j-i] != '?' and x[j] != y[j-i]:
                            tf = False
                            break
                    li.append(tf)

                m[(x, y)] = li

        answer = 7000


        for _a, _b, _c in itertools.permutations([a, b, c]):
            for x in range(len(_a)+1):
                for y in range(len(_b)+1):
                    if m[(_a, _b)][x] and m[(_b, _c)][y] and m[(_a, _c)][min(x+y, len(_a))]:
                        # ok
                        ll = max(len(_a), x + len(_b), x + y + len(_c))
                        answer = min(answer, ll)

        return answer


if __name__ == '__main__':

    # standard input
    a = input()
    b = input()
    c = input()

    # solve
    solution = Solution()
    answer = solution.solve(a, b, c)
    print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import repeat

def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge2(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb
  
  
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b = list(merge1(a,b))
  a_b2 = list(merge2(a,b))
  a_b3 = list(merge3(a,b))
  a_c = list(merge1(a,c))
  a_c2 = list(merge2(a,c))
  a_c3 = list(merge3(a,c))
  b_c = list(merge1(b,c))
  b_c2 = list(merge2(b,c))
  b_c3 = list(merge3(b,c))
  
  for i in a_b:
    for j in a_c:
      if j+lc <= i or i+lb <= j:
        return la
      if j-i in (b_c+b_c2+b_c3) and comp_dup(0,i,j,a,b,c):
        return la
        
  for i in a_b:
    for j in a_c2:
      if i+lb <= j:
        abc = min(abc, j+lc)
        break
      if j-i in (b_c2) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, j+lc)
        break
    for j in a_c3:
      if j+lc <= i:
        abc = min(abc, la-j)
        break
      if j-i in (b_c3) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, la-j)
        break
  
  for i in a_b2:
    if abc <= i+lb:
      break
    for j in a_c+a_c2:
      if j+lc  <= i:
        abc = min(abc, i+lb)
        break
      if j-i in (b_c+b_c3) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, i+lb)
        break
    if abc <= i+lb:
      break
    if b_c and la <= i+b_c[-1]:
      abc = min(abc, i+lb)
      break
    
    for j in a_c3:
      if abc <= i-j+lb:
        break
      if j+lc <= i:
        abc = min(abc, i-j+lb)
        break
      if j-i in b_c3 and comp_dup(0,i,j,a,b,c):
        abc = min(abc, i-j+lb)
        break
        
    for j in b_c2:
      if abc <= i+j+lc:
        break
      if la <= i+j:
        abc = min(abc, i+j+lc)
        break
      if i+j in a_c2 and comp_dup(0,i,i+j,a,b,c):
        abc = min(abc, i+j+lc)
        break
      
      
  for i in a_b3:
    if abc <= la-i:
      break
    for j in a_c+a_c3:
      if i+lb <= j:
        abc = min(abc, la-i)
        break
      if j-i in (b_c+b_c2) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, la-i)
        break
    if abc <= la-i:
      break
    if b_c and i+b_c[0]+lc <= 0:
      abc = min(abc, la-i)
      break
      
    for j in a_c2:
      if abc <= j-i+lc:
        break
      if i+lb <= j:
        abc = min(abc, j-i+lc)
        break
      if j-i in b_c2 and comp_dup(0,i,j,a,b,c):
        abc = min(abc, j-i+lc)
        break
        
    for j in b_c3:
      if abc <= la-i-j:
        break
      if i+j+lc <= 0:
        abc = min(abc, la-i-j)
        break
      if i+j in a_c3 and comp_dup(0,i,i+j,a,b,c):
        abc = min(abc, la-i-j)
        break
      
  
  for i in range(1,lc):
    if abc <= la+lb+i:
      break     
    for j in a_c2:
      if j-la-i in b_c3:
        return la+lb+i
    for j in b_c2:
      if j-la-i in a_c3:
        return la+lb+i
    
  return abc

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
import itertools


class Solution:

    def solve(self, a: str, b: str, c: str) -> int:

        m = {}
        for x, y in itertools.permutations([a, b, c], 2):
            if not (x, y) in m:
                li = []
                for i in range(len(x) + 1):
                    tf = True
                    for j in range(i, min(len(x), i + len(y))):
                        if x[j] != '?' and y[j-i] != '?' and x[j] != y[j-i]:
                            tf = False
                            break
                    li.append(tf)

                m[(x, y)] = li

        answer = 7000


        for _a, _b, _c in itertools.permutations([a, b, c]):
            for x in range(len(_a)+1):
                for y in range(len(_b)+1):
                    if m[(_a, _b)][x] and m[(_b, _c)][y] and m[(_a, _c)][min(x+y, len(_a))]:
                        # ok
                        ll = max(len(a), x + len(b), x + y + len(c))
                        answer = min(answer, ll)

        return answer


if __name__ == '__main__':

    # standard input
    a = input()
    b = input()
    c = input()

    # solve
    solution = Solution()
    answer = solution.solve(a, b, c)
    print(answer)

Submission status: Wrong Answer

Solution code:
import itertools


class Solution:

    def solve(self, a: str, b: str, c: str) -> int:

        m = {}
        for x, y in itertools.permutations([a, b, c], 2):
            if not (x, y) in m:
                li = []
                for i in range(len(x) + 1):
                    tf = True
                    for j in range(i, min(len(x), i + len(y))):
                        if x[j] != '?' and y[j-i] != '?' and x[j] != y[j-i]:
                            tf = False
                            break
                    li.append(tf)

                m[(x, y)] = li

        answer = 6000

        for _a, _b, _c in itertools.permutations([a, b, c]):
            for x in range(len(_a)+1):
                for y in range(len(_b)+1):
                    if m[(_a, _b)][x] and m[(_b, _c)][y] and m[(_a, _c)][min(x+y, len(_a))]:
                        # ok
                        ll = max(len(a), x + len(b), x + y + len(c))
                        answer = min(answer, ll)

        return answer


if __name__ == '__main__':

    # standard input
    a = input()
    b = input()
    c = input()

    # solve
    solution = Solution()
    answer = solution.solve(a, b, c)
    print(answer)

Submission status: Wrong Answer

Solution code:
a = input().strip()
b = input().strip()
c = input().strip()
kk = 2000
K = kk*2
na, nb, nc = len(a), len(b), len(c)
def ll(s, t):
    X = [0] * 100000
    ns, nt = len(s), len(t)
    for i in range(ns):
        for j in range(nt):
            if s[i] != t[j] and s[i] != "?" and t[j] != "?":
                X[j-i+K] = 1
    return X

ab = ll(a, b)
bc = ll(b, c)
ac = ll(a, c)
r = na+nb+nc
for i in range(-kk, kk+1):
    for j in range(-kk, kk+1):
        if (not ab[-i+K]) and (not ac[-j+K]) and (not bc[-j+i+K]):
            st = min(i, j, 0)
            en = max(i+nb, j+nc, na)
            r = min(en-st, r)
print(r)

Submission status: Wrong Answer

Solution code:
a = input().strip()
b = input().strip()
c = input().strip()
kk = 2000
K = kk*2
na, nb, nc = len(a), len(b), len(c)
def ll(s, t):
    X = [0] * (2*K+1)
    ns, nt = len(s), len(t)
    for i in range(ns):
        for j in range(nt):
            if s[i] != t[j] and s[i] != "?" and t[j] != "?":
                X[j-i+kk] = 1
    return X

ab = ll(a, b)
bc = ll(b, c)
ac = ll(a, c)
r = na+nb+nc
for i in range(-kk, kk+1):
    for j in range(-kk, kk+1):
        if (not ab[-i+kk]) and (not ac[-j+kk]) and (not bc[-j+i+kk]):
            st = min(i, j, 0)
            en = max(i+nb, j+nc, na)
            r = min(en-st, r)
print(r)

Submission status: Wrong Answer

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 merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    m = comp(a[i:],b)
    if m:
      yield i, (a[:i]+m+a[i+lb:], la)

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

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    m = comp(b[i:], a)
    if m:
      yield -i, (b[:i]+m+a[len(b)-i:], la+i)
  yield -lb, (b+a, la+lb)
  
  
  
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b = dict(merge1(a,b))
  a_b2 = dict(merge2(a,b))
  a_b3 = dict(merge3(a,b))
  a_c = dict(merge1(a,c))
  a_c2 = dict(merge2(a,c))
  a_c3 = dict(merge3(a,c))
  b_c = dict(merge1(b,c))
  b_c2 = dict(merge2(b,c))
  b_c3 = dict(merge3(b,c))
  
  for i,(d, ld) in a_b.items()|a_b2.items()|a_b3.items():
    for j, (e, le) in a_c.items()|a_c2.items()|a_c3.items():
      if j-i in b_c and comp(d[j-min(0,i):], c):
        abc = min(abc, ld)
        continue
      if j-i in b_c2 and comp(d[j-min(0,i):], c):
        abc = min(abc, ld)
        continue
      if j-i in b_c3 and comp(d[j-min(0,i):], c):
        abc = min(abc, ld)
        continue

  for i in range(1,lc):
    if abc < la+lb+i:
      break     
    for j, (e, le) in a_c2.items():
      if j-la-i in b_c3:
        return la+lb+i
    for j, (e, le) in b_c2.items():
      if j-la-i in a_c3:
        return la+lb+i
    
  return abc

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
import sys

def Z_algo2(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and (s[j] == s[i+j] or s[j] == '?' or s[i+j] == '?'):
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    return lcp

def Z_algo(s,t):
    lt = len(t)
    ls = len(s)
    l = [0]*lt
    for i in range(len(t)):
        j = 0
        while j < ls and i+j < lt and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
            j += 1
        l[i] = j
    return l

def main():
    a = list(map(ord, list(input())))
    b = list(map(ord, list(input())))
    c = list(map(ord, list(input())))

    l = [a, b, c]
    g = [[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            if i != j:
                g[i][j] = Z_algo(l[i],l[j])
    ans = sum(len(x) for x in l)
    for i in range(3):
        lli = len(l[i])
        for j in range(3):
            if i == j: continue
            k = 3-i-j
            llj = len(l[j])
            llk = len(l[k])
            gji = g[j][i]
            gkj = g[k][j]
            gki = g[k][i]
            li = [ii for ii in range(lli) if gji[ii] >= (lli-ii if lli - ii < llj else llj)]
            lj = [ii for ii in range(llj) if gkj[ii] >= (llj-ii if llj - ii < llk else llk)]
            lk = [ii for ii in range(lli) if gki[ii] >= (lli-ii if lli - ii < llk else llk)]
            if li:
                c = max(lli, min(li) + llj + llk)
                if ans > c: ans = c
            for ii in li:
                for jj in lj:
                    kk = ii + jj
                    if kk >= lli or gki[kk] >= (lli-kk if lli - kk < llk else llk):
                        c = max(lli, ii + llj, kk + llk)
                        if ans > c: ans = c
            for ii in li:
                for kk in lk:
                    if kk < ii + llj: continue
                    c = max(lli, ii + llj, kk + llk)
                    if ans > c: ans = c
    print(ans)

if __name__ == "__main__":
    ques = ord('?')
    main()

Submission status: Wrong Answer

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 merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    m = comp(a[i:],b)
    if m:
      yield i, (a[:i]+m+a[i+lb:], la)

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

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    m = comp(b[i:], a)
    if m:
      yield -i, (b[:i]+m+a[len(b)-i:], la+i)
  yield -lb, (b+a, la+lb)
  
  
  
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b = dict(merge1(a,b))
  a_b2 = dict(merge2(a,b))
  a_b3 = dict(merge3(a,b))
  a_c = dict(merge1(a,c))
  a_c2 = dict(merge2(a,c))
  a_c3 = dict(merge3(a,c))
  b_c = dict(merge1(b,c))
  b_c2 = dict(merge2(b,c))
  b_c3 = dict(merge3(b,c))
  
  for i,(d, ld) in a_b.items():
    for j, (e, le) in a_c.items():
      if j+lc<=i or i+lb<=j:
        return la
      if j-i in b_c and comp(d[j:], c):
        return la
      if j-i in b_c2 and comp(d[j:j+lb], c):
        return la
      if j-i in b_c3 and comp(d[i:], c[i-j:]):
        return la
  
  for i,(d, ld) in a_b2.items():
    if abc <= ld:
      break
    for j, (e, le) in a_c.items()|a_c2.items():
      if j+lc<=i:
        abc = min(abc, ld)
        break
      if j-i in b_c and comp(d[j:la], c):
        abc = min(abc, ld)
        break
      if j-i in b_c3 and comp(d[i:la], c[i-j:]):
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in b_c.items():
      if la<=i+j:
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in a_c3.items():
      if j+lc<=i:
        abc = min(abc, ld-j)
        break
      if j-i in b_c3 and comp(d[i:], c[i-j:]):
        abc = min(abc, ld-j)
        break
    for j, (e, le) in b_c2.items():
      if la<=i+j:
        abc = min(abc, i+le)
        break
      if i+j in a_c2 and comp(d[i+j:la], c):
        abc = min(abc, i+le)
        break
      
      
  for i,(d, ld) in a_b3.items():
    if abc <= ld:
      break
    for j, (e, le) in a_c.items()|a_c3.items():
      if i+lb <= j:
        abc = min(abc, ld)
        break
      if j-i in b_c and comp(d[j-i+lc-1:-1:-1], c[::-1]):
        abc = min(abc, ld)
        break
      if j-i in b_c2 and comp(d[lb-1:-i-1:-1], c[i-j+lb-1::-1]):
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
    for j, (e, le) in b_c.items():
      if i+j+lc<=0:
        abc = min(abc, ld)
        break
    if abc <= ld:
      break
      
    for j, (e, le) in a_c3.items():
      if i+lb<=j:
        abc = min(abc, le-i)
        break
      if j-i in b_c2 and comp(d[j-i:lb], c):
        abc = min(abc, le-i)
        break
      
    for j, (e, le) in b_c3.items():
      if i+j+lc<=0:
        abc = min(abc, ld-j)
        break
      if i+j in a_c3 and comp(d[-i:], c[-i-j:]):
        abc = min(abc, ld-j)
        break
  
  for i in range(1,lc):
    if abc < la+lb+i:
      break     
    for j, (e, le) in a_c2.items():
      if j-la-i in b_c3:
        return la+lb+i
    for j, (e, le) in b_c2.items():
      if j-la-i in a_c3:
        return la+lb+i
    
  return abc

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
# E - Three Substrings

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

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

M = max(A, B, C)
cons = 6*M
a_not_match_b = [False] * 2 * cons
b_not_match_c = [False] * 2 * cons
a_not_match_c = [False] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)):
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[j-i+cons] = True
    return l

a_not_match_b = fill_match_list(a, b, a_not_match_b)
b_not_match_c = fill_match_list(b, c, b_not_match_c)
a_not_match_c = fill_match_list(a, c, a_not_match_c)

ans = 3*M
for b_idx in range(-2*M, 2*M):
    for c_idx in range(-2*M, 2*M):
        if not a_not_match_b[b_idx + cons] and not a_not_match_c[c_idx + cons] and not b_not_match_c[c_idx - b_idx + cons]:
            ans = min(ans, max(A, B + b_idx, C + c_idx) - min(0, b_idx, c_idx))

print(ans)

Submission status: Wrong Answer

Solution code:
# E - Three Substrings

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

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

M = max(A, B, C)
cons = 6*M
a_not_match_b = [False] * 2 * cons
b_not_match_c = [False] * 2 * cons
a_not_match_c = [False] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)):
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = True
    return l

a_not_match_b = fill_match_list(a, b, a_not_match_b)
b_not_match_c = fill_match_list(b, c, b_not_match_c)
a_not_match_c = fill_match_list(a, c, a_not_match_c)

ans = 3*M
for b_idx in range(-2*M, 2*M):
    for c_idx in range(-2*M, 2*M):
        if not a_not_match_b[-b_idx + cons] and not a_not_match_c[-c_idx + cons] and not b_not_match_c[b_idx - c_idx + cons]:
            ans = min(ans, max(A, B + b_idx, C + c_idx) - min(0, b_idx, c_idx))

print(ans)

Submission status: Wrong Answer

Solution code:
# E - Three Substrings

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

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

M = max(A, B, C)
cons = 6*M
a_not_match_b = [False] * 2 * cons
b_not_match_c = [False] * 2 * cons
c_not_match_a = [False] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)):
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = True
    return l

a_not_match_b = fill_match_list(a, b, a_not_match_b)
b_not_match_c = fill_match_list(b, c, b_not_match_c)
c_not_match_a = fill_match_list(c, a, c_not_match_a)

ans = 3*M
for rel_a_idx_against_b in range(-2*M, 2*M):
    for rel_c_idx_against_b in range(-2*M, 2*M):
        if not a_not_match_b[rel_a_idx_against_b + cons] and not b_not_match_c[-rel_c_idx_against_b + cons] and not c_not_match_a[rel_c_idx_against_b - rel_a_idx_against_b + cons]:
            ans = min(ans, max(B, A + rel_a_idx_against_b, C + rel_c_idx_against_b) - min(0, rel_a_idx_against_b, rel_c_idx_against_b))

print(ans)

Submission status: Wrong Answer

Solution code:
# E - Three Substrings

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

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

M = max(A, B, C)
cons = 6*M
a_match_b = [True] * 2 * cons
b_match_c = [True] * 2 * cons
c_match_a = [True] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)):
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = False
    return l

a_match_b = fill_match_list(a, b, a_match_b)
b_match_c = fill_match_list(b, c, b_match_c)
c_match_a = fill_match_list(c, a, c_match_a)

ans = 3*M
for rel_a_idx_against_b in range(-2*M, 2*M):
    for rel_c_idx_against_b in range(-2*M, 2*M):
        if a_match_b[rel_a_idx_against_b + cons] and b_match_c[-rel_c_idx_against_b + cons] and c_match_a[rel_c_idx_against_b - rel_a_idx_against_b + cons]:
            ans = min(ans, max(B, A + rel_a_idx_against_b, C + rel_c_idx_against_b) - min(0, rel_a_idx_against_b, rel_c_idx_against_b))

print(ans)

Submission status: Wrong Answer

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

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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n + m + l), [True]*(n + m + l), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(m):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    BC.append(m)

    res = float('inf')
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n + m + l:
                    continue
                elif AC[i + j]:
                    res = min(res, n + m + l, max(n, i + m, i + j + l))
    return res

def main():
    a = input()
    b = input()
    c = input()

    ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def solve(a: str, b: str, c: str):
    permutation = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]
    abc = [a,b,c]
    ans = 10**4

    for i_1,j_1,k_1 in permutation:
        A = abc[i_1]
        B = abc[j_1]
        C = abc[k_1]
        LENA = len(A)
        LENB = len(B)
        LENC = len(C)

        AB = [False]*(LENA+1)
        BC = [False]*(LENB+1)
        AC = [False]*(LENA)+[True]*(1+LENB)
        AB[-1] = True
        BC[-1] = True

        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENB+i)):
                if A[j] != B[j-i] and A[j] != "?" and B[j-i] != "?":
                    break
            else:
                AB[i] = True

        for i in range(LENB): # Bのindex
            for j in range(i,min(LENB,LENC+i)):
                if B[j] != C[j-i] and B[j] != "?" and C[j-i] != "?":
                    break
            else:
                BC[i] = True

        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENC+i)):
                if A[j] != C[j-i] and A[j] != "?" and C[j-i] != "?":
                    break
            else:
                AC[i] = True
        
        # x: AとBがどれだけずれてるか
        # y: BとCがどれだけずれてるか
        length = 10**4
        for x in range(LENA+1):
            for y in range(LENB+1):
                if AB[x] and BC[y] and AC[x+y]:
                    length = min(length,max(LENA,x+LENB,x+y+LENC))
        ans = min(ans,length)
 
    print(ans)
    return


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

Solution code:
# E - Three Substrings

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

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

M = max(A, B, C)
cons = 20000
rel_match_b_against_a = [True] * 2 * cons
rel_match_b_against_c = [True] * 2 * cons
rel_match_c_against_a = [True] * 2 * cons

for rel_idx in range(-B+1, A):
    if rel_idx < 0:
        for i in range(min(A, rel_idx + B)):
            if a[i] != b[i + rel_idx] and a[i] != "?" and b[i + rel_idx] != "?":
                rel_match_b_against_a[rel_idx + cons] = False
                break
    else:
        for i in range(min(A - rel_idx, B)):
            if a[i + rel_idx] != b[i] and a[i + rel_idx] != "?" and b[i] != "?":
                rel_match_b_against_a[rel_idx + cons] = False
                break

for rel_idx in range(-B+1, C):
    if rel_idx < 0:
        for i in range(min(C, rel_idx + B)):
            if c[i] != b[i + rel_idx] and c[i] != "?" and b[i + rel_idx] != "?":
                rel_match_b_against_c[rel_idx + cons] = False
                break
    else:
        for i in range(min(C - rel_idx, B)):
            if c[i + rel_idx] != b[i] and c[i + rel_idx] != "?" and b[i] != "?":
                rel_match_b_against_c[rel_idx + cons] = False
                break

for rel_idx in range(-C+1, A):
    if rel_idx < 0:
        for i in range(min(A, rel_idx + C)):
            if a[i] != c[i + rel_idx] and a[i] != "?" and c[i + rel_idx] != "?":
                rel_match_c_against_a[rel_idx + cons] = False
                break
    else:
        for i in range(min(A - rel_idx, C)):
            if a[i + rel_idx] != c[i] and a[i + rel_idx] != "?" and c[i] != "?":
                rel_match_c_against_a[rel_idx + cons] = False
                break

ans = 3*M
for rel_idx_b_against_a in range(-2*M, 2*M):
    for rel_idx_c_against_a in range(-2*M, 2*M):
        if rel_match_b_against_a[rel_idx_b_against_a + cons] and rel_match_c_against_a[rel_idx_c_against_a + cons] and rel_match_b_against_c[rel_idx_b_against_a - rel_idx_c_against_a + cons]:
            ans = min(ans, max(A, B + rel_idx_b_against_a, C + rel_idx_c_against_a) - min(0, rel_idx_b_against_a, rel_idx_c_against_a))

print(ans)

Submission status: Wrong Answer

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

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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n + m + l), [True]*(n + m + l), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(m):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    BC.append(m)

    res = float('inf')
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n + m + l:
                    continue
                elif AC[i + j]:
                    res = min(res, max(n, i + m, i + j + l))
    return res

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

ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
print(ans)