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: Runtime Error

Solution code:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))
  
def comp33(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]) and comp(a[m-i:n-i],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp33(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Runtime Error

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


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


def check(s, t):
    check_st = {i: True for i in range(-5000, 5001)}
    for i in range(len(s)):
        for j in range(len(t)):
            if not comp(s[i], t[j]):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ca = check(c, a)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ca[c_idx] and check_bc[b_idx - c_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k.i
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Runtime Error

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

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

M = 2000

ab, ac, bc = [], [], []
for _  in range(10000):
    ab.append(0)
    ac.append(0)
    bc.append(0)


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

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

print(ans)

Submission status: Runtime Error

Solution code:
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=map(len,[S[t]for t in X]);q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import*;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Runtime Error

Solution code:
from itertools import *
from heapq import *
from collections import OrderedDict

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  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 comp3(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

def delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))

  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
from itertools import *
from heapq import *
from collections import defaultdict

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

def delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  mid_set = {k:set(v) for k,v in mid.items()}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right_set = {k:set(v) for k,v in right.items()}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid_set[1,2]|right_set[1,2] or i-j in right_set[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right_set[c,b] if i>j else j-i in mid_set[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  return len_a + len_b + len_c

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

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and ac[min(na,l+r)]==1:
                alt=max(na,l+nb,l+r+nc)
                if alt<rt:
                    rt=alt

        if ab[l]==1:
            for r in range(l+nb,na+1):
                if ac[r]==1:
                    alt=max(na,r+nc)
                    if alt<rt:
                        rt=alt
    return rt
    
a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))
ans=10**5
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


a = S()
b = S()
c = S()
total_len = len(a) + len(b) + len(c)

def check(x, y):
    # xの後にy
    x_len = len(x)
    L = [0] * (x_len + 1)
    for gap in range(x_len + 1):
        for j in range(x_len + 1):
            if gap + j >= x_len:
                continue
            elif x[gap + j] != y[j] and x[gap + j] != '?' and y[j] != '?':
                break
        else:
            L[gap] = 1
    return L


ans = total_len
for i, j, k in permutations((a, b, c)):
    ij_list = check(i, j)
    jk_list = check(j, k)
    ik_list = check(i, k)
    i_len = len(i)
    j_len = len(j)
    k_len = len(k)
    for ij_gap in range(len(i) + 1):
        for jk_gap in range(len(j) + 1):
            if ij_list[ij_gap] == 0 or jk_list[jk_gap] == 0:
                continue
            if j_len - ij_gap - jk_gap > 0 and ik_list[j_len - ij_gap - jk_gap] == 0:
                continue
            ans = min(ans, max(ij_gap + jk_gap + k_len, ij_gap + j_len, i_len))

print(ans)

Submission status: Runtime Error

Solution code:
# input
A = input()
B = input()
C = input()

# process
def eq(c, d):
    if c != d and c != '?' and d != '?':
        return False
    return True

# sを固定したとき、tの開始位置ごとにsと重なるかを確認(1999が中央)
def check(s, t, st):
    for i in range(len(s)):
        for j in range(len(t)):
            if not eq(s[i], t[j]):
                st[i-j+4999] = False

ab = [True]*10000
ac = [True]*10000
bc = [True]*10000
check(A, B, ab)
check(A, C, ac)
check(B, C, bc)

ans = 6000
bcnum = len(B)+len(C)
for i in range(-bcnum, bcnum):
    for j in range(-bcnum, bcnum):
        if ab[i+4999] and ac[j+4999] and bc[j-i+4999]:
            l = min(0, i, j)
            r = max(len(A), len(B)+i, len(C)+j)
            ans = min(ans, r-l)

# output
# print(ab[4999-len(B)+1:4999+len(A)])
# print(ac[4999-len(C)+1:4999+len(A)])
# print(bc[4999-len(C)+1:4999+len(B)])

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(nb,na-i)):
            if (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                if na+nb+nc-(na-l)-(nb-r)<rt:
                    rt=max(na,na+nb+nc-(na-l)-(nb-r))
                    al,ar=l,r
    return max(rt,na)

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

na,nb,nc=map(len,(a,b,c))
ans=inf
strs=[a,b,c]
chMat=[[check(strs[j],strs[i]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                if na+nb+nc-(na-l)-(nb-r)<rt:
                    rt=max(na,na+nb+nc-(na-l)-(nb-r))
                    al,ar=l,r
    return max(rt,na)

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

na,nb,nc=map(len,(a,b,c))
ans=inf
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Runtime Error

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

memo = [[[1]*4000 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]
    stt0 = 0
    for stt1 in range(0,l0+1):
        if not memo[i][j][stt1-stt0]:
            continue
        l01 = max(l0,stt1+l1)
        for stt2 in range(stt1,l01+1):
            if not memo[j][k][stt2-stt1]:
                continue
            if not memo[i][k][stt2-stt0]:
                continue
            l012 = max(l01,stt2+l2)
            ans = min(ans,l012)
print(ans)

Submission status: Runtime Error

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

memo = [[[1]*4000 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]
    stt0 = 0
    for stt1 in range(0,l0+1):
        if not memo[i][j][stt1-stt0]:
            continue
        l01 = max(l0,stt1+l1)
        for stt2 in range(stt1,l01+1):
            if not memo[j][k][stt2-stt1]:
                continue
            if not memo[i][k][stt2-stt0]:
                continue
            l012 = max(l01,stt2+l2)
            ans = min(ans,l012)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import time
if __name__ == "__main__":
    a = input()
    b = input()
    c = input()
    s = 0
    A = len(a)
    B = len(b)
    C = len(c)
    K = 4000
    #ab,ac,bcに対して相対位置を-2000~2000までずらした時に矛盾が生じないかどうかを前計算する
    #time1 = time.time()
    ab =[True]*(K*2+1)
    ac = [True]*(K*2+1)
    bc = [True] *(K*2+1)
    #print(time.time()-time1)
    #定数倍高速化を試みる
    def match(s1,s2,ss):
        len2 =len(s2)
        len1 = len(s1)
        for i in range(-len2,len1):
            #文字列s1の左端を0として、s2の左端がiに存在する
            for j in range(max(i,0),min(len1,len2+i)):
                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] = False
                    break
    match(a,b,ab)
    match(a,c,ac)
    match(b,c,bc)
    #print(time.time()-time1)
    ans = 6000
    # aの左端を０とした時に、b,cの位置をi,jとして全探索する
    for i in range(-K,K+1):
        if ab[i] == False: continue
        for j in range(-K,K+1):
            if ac[j] and bc[j-i]:
                #矛盾がないパターンなのでansを更新
                left = min(0,min(i,j))
                right = max(A,max(B+i,C+j))
                ans = min(ans,right- left)
            #if i%1000 == 0 and j%1000 == 0:
                #print(i,j,time.time()-time1)
    print(ans)
    #print(time.time()-time1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import time
if __name__ == "__main__":
    a = input()
    b = input()
    c = input()
    s = 0
    A = len(a)
    B = len(b)
    C = len(c)
    K = 4000
    #ab,ac,bcに対して相対位置を-2000~2000までずらした時に矛盾が生じないかどうかを前計算する
    #time1 = time.time()
    ab =[True]*(K*2+1)
    ac = [True]*(K*2+1)
    bc = [True] *(K*2+1)
    #print(time.time()-time1)
    #定数倍高速化を試みる
    def match(s1,s2,ss):
        len2 =len(s2)
        len1 = len(s1)
        for i in range(-len2,len1):
            #文字列s1の左端を0として、s2の左端がiに存在する
            for j in range(max(i,0),min(len1,len2+i)):
                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] = False
                    break
    match(a,b,ab)
    match(a,c,ac)
    match(b,c,bc)
    #print(time.time()-time1)
    ans = 6000
    # aの左端を０とした時に、b,cの位置をi,jとして全探索する
    for i in range(-K,K+1):
        if ab[i] == False: continue
        for j in range(-K,K+1):
            if ac[j] and bc[j-i]:
                #矛盾がないパターンなのでansを更新
                left = min(0,min(i,j))
                right = max(A,max(B+i,C+j))
                ans = min(ans,right- left)
            if i%1000 == 0 and j%1000 == 0:
                #print(i,j,time.time()-time1)
    print(ans)
    #print(time.time()-time1)