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:
#!/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**9

    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**9
        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(x+LENB,LENA,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:
#!/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**9

    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**9
        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(x+LENB,LENA,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:
#!/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 + m + l):
        if i > n:
            continue
        for j in BC:
            if i + j >= n + m + l:
                res = min(res, max(n, i + m, i + j + l))
            elif AB[i] and 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)

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)
    
    res = float('inf')
    for i in range(n + m + l):
        for j in BC:
            if i + j >= n + m + l:
                continue
            elif AB[i] and AC[i + j]:
                res = min(res, max(n, max(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)

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)
    
    res = float('inf')
    for i in range(n + m + l):
        for j in BC:
            if i + j >= n + m + l:
                res = min(res,max(n, max(i + m, i + j + l)))
            elif AB[i] and AC[i + j]:
                res = min(res, max(n, max(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)

Submission status: Wrong Answer

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


def stack2(a, b):
    max_reduce = min(len(a), len(b))
    reduce = 0
    stacked = a + b
    for i in reversed(range(max_reduce)):
        a_end = a[len(a)-i-1:]
        b_begin = b[:i+1]
        flag = True
        for j in range(len(a_end)):
            if a_end[j] != b_begin[j] and a_end[j] != '?' and b_begin[j] != '?':
                flag = False
                break
        if flag == True:
            reduce = len(a_end)
            a_begin = a[:len(a) - i - 1]
            b_end = b[i+1:]
            mid = ''
            for k in range(i+1):
                if a_end[k] != '?':
                    letter = a_end[k]
                else:
                    letter = b_begin[k]
                mid = mid + letter
            stacked = a_begin + mid + b_end
            break
    return stacked, reduce

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

r1 = stack2(a, b)[1] + stack2(stack2(a, b)[0], c)[1]
r2 = stack2(a, c)[1] + stack2(stack2(a, c)[0], b)[1]
r3 = stack2(b, a)[1] + stack2(stack2(b, a)[0], c)[1]
r4 = stack2(b, c)[1] + stack2(stack2(b, c)[0], a)[1]
r5 = stack2(c, a)[1] + stack2(stack2(c, a)[0], b)[1]
r6 = stack2(c, b)[1] + stack2(stack2(c, b)[0], a)[1]
r7 = stack2(a, b)[1] + stack2(c, stack2(a, b)[0])[1]
r8 = stack2(a, c)[1] + stack2(b, stack2(a, c)[0])[1]
r9 = stack2(b, a)[1] + stack2(c, stack2(b, a)[0])[1]
r10 = stack2(b, c)[1] + stack2(a, stack2(b, c)[0])[1]
r11 = stack2(c, a)[1] + stack2(b, stack2(c, a)[0])[1]
r12 = stack2(c, b)[1] + stack2(a, stack2(c, b)[0])[1]


r = max(r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12)

print(S-r)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = N
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue

                rx = len(x) - i
                ry = len(y) - j
                rxy = rx - len(y)
                s = len(x)
                if rx >= len(y):
                    pass
                else:
                    s += len(y) - rx

                if rxy >= len(z):
                    pass
                elif ry >= len(z):
                    pass
                else:
                    s += len(z) - ry
                ans = min(ans, s)
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = N
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue

                rx = len(x) - i
                ry = len(y) - j
                rxy = rx - len(y)
                s = len(x)
                if rx > len(y):
                    pass
                else:
                    s += len(y) - rx

                if rxy > len(z):
                    pass
                elif ry > len(z):
                    pass
                else:
                    s += len(z) - ry
                ans = min(ans, s)
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = N
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue

                s = x
                s = len(x)
                if len(x) - i < len(y):
                    s += len(y) - (len(x)-i)
                if len(y) - j < len(z):
                    s += len(z) - (len(y)-i)

                ans = min(ans, s)
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = N
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue

                s = x
                if len(x) - i < len(y):
                    s += y[len(x) - i:]
                if len(y) - j < len(z):
                    s += z[len(x) - i:]

                ans = min(ans, len(s))
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from re import *

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

ans = []

a = a.replace('?', '.')
b = b.replace('?', '.')
c = c.replace('?', '.')

# print(a, b, c)

mx = 0
tas, tes = "", ""
for i in range(len(b)):
    # print(search(b[0:i+1]+'$', a))
    # print(search('^'+b[len(b)-1-i:len(b)+1], a))
    ta = search(b[0:i+1]+'$', a)
    if ta and mx < len(ta.group()):
        mx = len(ta.group())
        tas = ta.group()
    te = search('^'+b[len(b)-1-i:len(b)+1], a)
    if te and mx < len(te.group()):
        mx = len(te.group())
        tes = te.group()

# print("------------------------------")

if len(tas) > len(tes):
    s = a + b[len(tas):]
    # print(s)
else:
    s = b[:len(b)-len(tes)] + a
    # print(s)

# print("------------------------------")

mx = 0
tas, tes = "", ""
for i in range(len(c)):
    # print(findall(c[0:i+1]+'$', s))
    # print(findall('^'+c[len(b)-1-i:len(b)+1], s))
    ta = findall(c[0:i+1]+'$', s)
    if ta and mx < len(ta[0]):
        mx = len(ta[0])
        tas = ta[0]
    te = findall('^'+c[len(b)-1-i:len(b)+1], s)
    if te and mx < len(te[0]):
        mx = len(te[0])
        tes = te[0]

# print("------------------------------")

if len(tas) > len(tes):
    ss = s + c[len(tas):]
    # print(ss)
else:
    ss = c[:len(c)-len(tes)] + s
    # print(ss)

ans.append(ss)

# print("------------------------------")

mx = 0
tas, tes = "", ""
for i in range(len(c)):
    # print(search(c[0:i+1]+'$', b))
    # print(search('^'+c[len(c)-1-i:len(c)+1], b))
    ta = search(c[0:i+1]+'$', b)
    if ta and mx < len(ta.group()):
        mx = len(ta.group())
        tas = ta.group()
    te = search('^'+c[len(c)-1-i:len(c)+1], b)
    if te and mx < len(te.group()):
        mx = len(te.group())
        tes = te.group()

# print("------------------------------")

if len(tas) > len(tes):
    s = b + c[len(tas):]
    # print(s)
else:
    s = c[:len(c)-len(tes)] + b
    # print(s)

# print("------------------------------")

mx = 0
tas, tes = "", ""
for i in range(len(a)):
    # print(findall(a[0:i+1]+'$', s))
    # print(findall('^'+a[len(a)-1-i:len(a)+1], s))
    ta = findall(a[0:i+1]+'$', s)
    if ta and mx < len(ta[0]):
        mx = len(ta[0])
        tas = ta[0]
    te = findall('^'+a[len(a)-1-i:len(a)+1], s)
    if te and mx < len(te[0]):
        mx = len(te[0])
        tes = te[0]

# print("------------------------------")

if len(tas) > len(tes):
    ss = s + a[len(tas):]
    # print(ss)
else:
    ss = a[:len(a)-len(tes)] + s
    # print(ss)

ans.append(ss)

# print("------------------------------")

mx = 0
tas, tes = "", ""
for i in range(len(a)):
    # print(search(a[0:i+1]+'$', c))
    # print(search('^'+a[len(a)-1-i:len(a)+1], c))
    ta = search(a[0:i+1]+'$', c)
    if ta and mx < len(ta.group()):
        mx = len(ta.group())
        tas = ta.group()
    te = search('^'+a[len(a)-1-i:len(a)+1], c)
    if te and mx < len(te.group()):
        mx = len(te.group())
        tes = te.group()

# print("------------------------------")

if len(tas) > len(tes):
    s = c + a[len(tas):]
    # print(s)
else:
    s = a[:len(a)-len(tes)] + c
    # print(s)

# print("------------------------------")

mx = 0
tas, tes = "", ""
for i in range(len(b)):
    # print(findall(b[0:i+1]+'$', s))
    # print(findall('^'+a[len(b)-1-i:len(b)+1], s))
    ta = findall(b[0:i+1]+'$', s)
    if ta and mx < len(ta[0]):
        mx = len(ta[0])
        tas = ta[0]
    te = findall('^'+b[len(b)-1-i:len(b)+1], s)
    if te and mx < len(te[0]):
        mx = len(te[0])
        tes = te[0]

# print("------------------------------")

if len(tas) > len(tes):
    ss = s + b[len(tas):]
    # print(ss)
else:
    ss = b[:len(b)-len(tes)] + s
    # print(ss)

ans.append(ss)

# print("------------------------------")

# print(ans)

print(len(min(ans)))

Submission status: Wrong Answer

Solution code:
print("test")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = len(x) + len(y) + len(z)
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        # print(xy, yz, xz, x, y, z)
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue
                ans = min(ans, N - (len(A)-i) - (len(B)-j))
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        return m

    def f(x, y, z):
        N = len(x) + len(y) + len(z)
        ans = len(x) + len(y) + len(z)
        xy = g(x, y)
        yz = g(y, z)
        xz = set(g(x, z))
        for i in xy:
            for j in yz:
                if i+j < len(x) and i + j not in xz:
                    continue
                ans = min(ans, N - (len(A)-i) - (len(B)-j))
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))

    # D = '?'*2000
    # print(slv(D, D, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A = len(a)
B = len(b)
C = len(c)
def solve(d1,d2,n,m,l):
  for i in range(n):
    for j in range(m):
      if not(match(d1[i],d2[j])):
        l[i-j+10000]=True
        continue
  return l
ab = solve(a,b,A,B,ab)
ac = solve(a,c,A,C,ac)
bc = solve(b,c,B,C,bc)
ans = 6000

      
print(ans)

Submission status: Wrong Answer

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


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

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+[1]

ab=check(a,b)
ba=check(b,a)
cb=check(c,b)
bc=check(b,c)
ac=check(a,c)
ca=check(c,a)

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    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):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

show_flg=False
z=a,b,c,ab,bc,ac;x=tri_check(*z);show(x,z)
ans=x
z=a,c,b,ac,cb,ab;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=b,a,c,ba,ac,bc;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=b,c,a,bc,ca,ba;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=c,a,b,ca,ab,cb;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=c,b,a,cb,ba,ca;x=tri_check(*z);show(x,z)
ans=min(ans,x)

print(ans)