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: Accepted

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 = g(x, z)
        # print(xy, yz, xz)
        xz_set = set(xz)
        for i in xy:
            for j in yz:
                if i + j < len(x) and i + j in xz_set:
                    s = max(i + len(y), i + j + len(z), len(x))
                elif i + j < len(x) and i + len(y) :
                    l = bisect.bisect_left(xz, i+len(y))
                    if l >= len(xz):
                        continue
                    k = xz[l]
                    # print(k, xz)
                    s = max(i + len(y), k + len(z), len(x))
                elif  i + j >= len(x):
                    s = max(i + len(y), i + j + len(z), len(x))
                else:
                    continue
                # print(x, y, z, i, j, s)
                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 ref(A, B, C):
    def f(x, y):
        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:
                if len(y) > len(x)-i:
                    s = x + y[len(x)-i:]
                    s = list(s)
                    for j in range(len(x)-i):
                        if (x[i+j] == '?' and y[j] != '?'):
                            s[i+j] = y[j]
                    yield ''.join(s)
                else:
                    s = list(x)
                    for j in range(len(y)):
                        if (x[i+j] == '?' and y[j] != '?'):
                            s[i+j] = y[j]
                    yield ''.join(s)
        yield x + y
    ans = INF
    for x, y, z in permutations((A, B, C)):
        # print('-----', x, y, z)
        for xy in f(x, y):
            for xyz in f(xy, z):
                # print(xyz, len(xyz), xy)
                ans = min(ans, len(xyz))
    return ans

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


    # # A, B, C = ['b', 'cacdd', 'b']
    # # A, B, C = ['d', 'acadcdac', 'ca']
    # # A, B, C = ['ab?b', 'bb', 'bc?']
    # # A, B, C = ['?aaa', 'b?ac', 'b?a?a']
    # # A, B, C = ['acb', 'b??bc', 'cccbc?b']
    # A, B, C = ['?bbbb', 'aa', 'cccba?ca']
    # # A, B, C = ['abba', '?cb', 'ccacba?a']
    # print(slv(A, B, C))
    # print(ref(A, B, C))



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

    # for _ in range(10000):
    #     cs = 'abc?'
    #     A = ''.join(random.choices(cs, k=random.randint(1, 10)))
    #     B = ''.join(random.choices(cs, k=random.randint(1, 10)))
    #     C = ''.join(random.choices(cs, k=random.randint(1, 10)))
    #     a = slv(A, B, C)
    #     b = ref(A, B, C)
    #     if a != b:
    #         print(A)
    #         print(B)
    #         print(C)
    #         print(a, b)
    #         break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def match(s, t, ls, lt, i):
    return all(s[i + j] == '?' or t[j] == '?' or s[i + j] == t[j] for j in range(min(ls - i, lt)))


a = input()
b = input()
c = input()
la, lb, lc = len(a), len(b), len(c)

ab = [match(a, b, la, lb, i) for i in range(0, la)] + [True] * 8000
ac = [match(a, c, la, lc, i) for i in range(0, la)] + [True] * 8000
bc = [match(b, c, lb, lc, i) for i in range(0, lb)] + [True] * 8000
ba = [match(b, a, lb, la, i) for i in range(1, lb)] + [True] * 8000
ca = [match(c, a, lc, la, i) for i in range(1, lc)] + [True] * 8000
cb = [match(c, b, lc, lb, i) for i in range(1, lc)] + [True] * 8000
ab.extend(reversed(ba))
ac.extend(reversed(ca))
bc.extend(reversed(cb))

ans = la + lb + lc

for db in range(-lb - lc, la + lc + 1):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(-lb - lc, la + lb + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc) - min(0, db, dc))

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

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

def main():
    def same(x,y):
        xn,yn=len(x),len(y)
        # x,yの一致する位置を調べる
        res = [True] * 4005
        for i in range(xn):
            for c0, c1 in zip(x[i:], y):
                if c0 != q and c1 != q and c0 != c1:
                    res[i] = False
                    break
        return res

    q=ord("?")
    ss=[[ord(c) for c in SI()] for _ in range(3)]
    # 一致を調べる
    eq=[[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            if i==j:continue
            eq[i][j]=same(ss[i],ss[j])
    # 位置を全探索
    ans=sum(len(ss[i]) for i in range(3))
    for si,sj,sk in permutations(range(3)):
        for i in range(len(ss[si])+1):
            for j in range(max(len(ss[sj]),len(ss[si])-i)+1):
                if eq[si][sj][i] and eq[sj][sk][j] and eq[si][sk][i+j]:
                    cur=max(len(ss[si]),len(ss[sj])+i,len(ss[sk])+i+j)
                    ans=min(ans,cur)
    print(ans)

main()

Submission status: Accepted

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

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

mod = 10**9 + 7

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

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

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

def is_match(c1,c2):
    if c1 == '?' or c2 == '?' or c1 == c2:
        return True
    else:
        return False

def prefix_match_len(x,y):
    len_list = []
    n = len(x)
    m = len(y)
    for i in range(n):
        match = 0
        for j in range(i,min(i+m,n)):
            if is_match(x[j],y[j-i]):
                match += 1
            else:
                break
        len_list.append(match)
    return len_list

def concat(x,y,xy):
    index_list = []
    n = len(x)
    m = len(y)
    for i in range(n):
        if xy[i] == min(n-i,m):
            index_list.append(i)
    index_list.append(n)
    return index_list

def concat2(x,y,z,xz,yz,zy,index_list):
    n1 = len(x)
    n2 = len(y)
    m = len(z)
    candidate = []
    for i in index_list:
        flag = False
        for j in range(max(n1,n2+i)):
            if j <= n1-1:
                if xz[j] != min(n1-j,m):
                    continue
            if j >= i:
                if n2-j+i >= 1 and yz[j-i] != min(n2-j+i,m):
                    continue
            else:
                if m-i+j >= 1 and zy[i-j] != min(m-i+j,n2):
                    continue
            flag = True
            candidate.append(max(n1,n2+i,j+m))
            break
        if not flag:
            candidate.append(max(n1,n2+i)+m)
    return min(candidate)

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

index_list = concat(a,b,ab)
ret1 = concat2(a,b,c,ac,bc,cb,index_list)
index_list = concat(a,c,ac)
ret2 = concat2(a,c,b,ab,cb,bc,index_list)
index_list = concat(b,a,ba)
ret3 = concat2(b,a,c,bc,ac,ca,index_list)
index_list = concat(b,c,bc)
ret4 = concat2(b,c,a,ba,ca,ac,index_list)
index_list = concat(c,a,ca)
ret5 = concat2(c,a,b,cb,ab,ba,index_list)
index_list = concat(c,b,cb)
ret6 = concat2(c,b,a,ca,ba,ab,index_list)

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

Submission status: Accepted

Solution code:

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

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

la = len(A)
lb  =len(B)
lc = len(C)

ml = max(la, lb, lc)

# 。a の左端の位置を 0 としたとき、他の文字列の左端の位置は −4000 から 4000 まで動く可能性があることに注意してください  より、４倍
ab = [False for _ in range(ml * 4 + 1)]
ac = [False for _ in range(ml * 4 + 1)]
bc = [False for _ in range(ml * 4 + 1)]

"""
下の２重forで(i,j) = (0,0)と(1,1)で配列のindexが同じになってしまうが、AとBの０文字目どうし、1文字目どうしを比べるのは、
同じところから先頭が始まっている場合なので、あるずれの配置について、全文字比較していることになる
i=0,j=2とかだとBのほうが左にある場合で、i=3,j=0だとAが左にある場合

ab[i - j]のindexに+2mlして、-2ml ~ 2ml 感を出したい気持ちがあるが、意味がないのでしない
"""


def main():

    for i in range(la):
        for j in range(lb):
            # すでにそのずらし方で文字が重ねられないことが分かっている場合はスキップ
            if ab[i - j]:
                continue
            # そのずらし方で重ねられない場合はTrue
            if not match(A[i], B[j]):
                ab[i - j] = True


    for i in range(la):
        for j in range(lc):
            # すでにそのずらし方で文字が重ねられないことが分かっている場合はスキップ
            if ac[i - j]:
                continue
            # そのずらし方で重ねられない場合はTrue
            if not match(A[i], C[j]):
                ac[i - j] = True

    for i in range(lb):
        for j in range(lc):
            # すでにそのずらし方で文字が重ねられないことが分かっている場合はスキップ
            if bc[i - j]:
                continue
            # そのずらし方で重ねられない場合はTrue
            if not match(B[i], C[j]):
                bc[i - j] = True       

    ans = la + lb + lc
    # BCAとかACBみたいにAの前後に並ぶ場合があるので、AとBの位置関係について±2*ml分探索（Aの頭が０の位置にあるとしてBをどこに置くか(それがi)ということ。）
    for i in range(-2*ml, 2*ml+1):
        # a,bについて、あるずらし方で重ねられない場合は飛ばす
        if ab[i]:
            continue
        # CBA,ABCのパターンがあるので～
        for j in range(-2*ml, 2*ml+1):
            if ac[j]:
                continue
            
            # ここでi,jはaの頭をindexの0としたときの位置にあたるので、B基準で見たときのCとの位置関係はj - iとなる
            # で、そのとき重ねられないならスキップ
            if bc[j - i]:
                continue

            # 文字列Sの左端のindex
            l = min(0, i, j)
            # 文字列Sの右端のindex
            r = max(0 + la, i + lb, j + lc)
            ans = min(ans, r - l)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc-3, la+lc+3):
        if not AB[i]:
            continue
        for j in range(-lb-lc-3, la+lb+3):
            if BC[j-i] and AC[j]:
                l = min(0, i, j)
                r = max(la, lb+i, lc+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations, product
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

MX = 2005
d = [[[0]*MX for _ in range(3)] for _ in range(3)]
# print(d)

s = [input() for _ in range(3)]
s.sort()
# print(s)

ans = MX*3
for sss in permutations(s):
    # print(sss)
    for i, j in product(range(3), repeat=2):
        for k in range(len(sss[i])):
            if i >= j: continue
            # print(i,j,k)
            ok = True
            for ni in range(k, len(sss[i])):
                nj = ni - k
                if nj >= len(sss[j]): break
                if sss[i][ni] == '?' or sss[j][nj] == '?': continue
                if sss[i][ni] != sss[j][nj]: ok = False
            d[i][j][k] = ok
    def f(i, j, k):
        if k >= len(sss[i]):
            return True
        return d[i][j][k]
    # print(sss)
    for x, y in product(range(MX), repeat=2):
        if f(0,1,x) == False: continue
        if f(1,2,y) == False: continue
        if f(0,2,x+y) == False: continue
        now = 0
        now = max(now, len(sss[0]))
        now = max(now, x+len(sss[1]))
        now = max(now, x+y+len(sss[2]))
        ans = min(ans, now)
print(ans)

Submission status: Accepted

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

"""
左端の順番を固定して考えた.(A,B,Cの順とする)
n : Aの長さ, m : Bの長さ, l : Cの長さ
AB : Aを固定した時のBが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
AC : Aを固定した時のCが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
BC : Bを固定した時のCが一致する先頭位置
　　⇒ Bの先頭からBの末尾+1の位置までm+1箇所考える + nがmより大きい場合はBとCが離れているかもしれないので, Aの末尾+1まで考える
　　⇒ Bの先頭からmax(n,m)+1の位置まで考える
"""

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+1), [True]*(n+1), []
    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(max(n,m)+1):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)

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

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

"""
左端の順番を固定して考えた.(A,B,Cの順とする)
n : Aの長さ, m : Bの長さ, l : Cの長さ
AB : Aを固定した時のBが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
AC : Aを固定した時のCが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
BC : Bを固定した時のCが一致する先頭位置
　　⇒ Bの先頭からBの末尾+1の位置までm+1箇所考える + nがmより大きい場合はBとCが離れているかもしれないので, Aの末尾+1まで考える
"""

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+1), [True]*(n+1), []
    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(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

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

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

ques = ord('?')

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):
  l = [0]*len(t)
  for i in range(len(t)):
    j = 0
    while j < len(s) and i+j < len(t) and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
      j += 1
    l[i] = j
  return l

a = list(map(ord, list(ns())))
b = list(map(ord, list(ns())))
c = list(map(ord, list(ns())))

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])
            # print(i,j,g[i][j])
ans = sum(len(x) for x in l)
for i in range(3):
    for j in range(3):
        if i == j: continue
        k = 3-i-j
        li = [ii for ii in range(len(l[i])) if g[j][i][ii] >= min(len(l[i]) - ii, len(l[j]))]
        lj = [ii for ii in range(len(l[j])) if g[k][j][ii] >= min(len(l[j]) - ii, len(l[k]))]
        lk = [ii for ii in range(len(l[i])) if g[k][i][ii] >= min(len(l[i]) - ii, len(l[k]))]

        for ii in li:
            for jj in lj:
                kk = ii + jj
                if kk >= len(l[i]) or g[k][i][kk] >= min(len(l[i]) - kk, len(l[k])):
                    c = max(len(l[i]), ii + len(l[j]), kk + len(l[k]))
                    if ans > c: ans = c
        for ii in li:
            for kk in lk:
                if kk < ii + len(l[j]): continue
                c = max(len(l[i]), ii + len(l[j]), kk + len(l[k]))
                if ans > c: ans = c
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = sum([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L3, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L3, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([L1, L2+i2, L3+i3]) - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))

Submission status: Accepted

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+1), [True]*(n+1), []
    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(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

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

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+1), [True]*(n+1), []
    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(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

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

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[i-j+2*K] = 1
    return X

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

Submission status: Accepted

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)): # d1のそれぞれの文字についてd2全体でチェック
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = True # d1始点から見たd2始点の相対位置に格納。d1の始点が原点(cons)にあり、かつd1[i]とd2[j]が同座標にある場合の、d2の始点の座標
    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: Accepted

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            li = len(s[i])
            for j in range(i, 3):
                lj = len(s[j])
                for k in range(li):
                    ok = True
                    for ni in range(k, li):
                        nj = ni - k
                        if nj >= lj:
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            ok = False
                    d[i][j][k] = ok
        f = lambda i, j, k: True if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if not f(0, 1, x):
                    continue
                if not f(1, 2, y):
                    continue
                if not f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                ans = min(ans, now)
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Accepted

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[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: Accepted

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+[True]*2010
        AC = [False]*(LENA)+[True]*(2010)
        AB[LENA] = 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(2001+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()