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:
a = input()
b = input()
c = input()

ordA = ord('a')
def convert(s, flag):
    ret = 0
    for c in s:
        ret <<= 26
        if c == '?':
            if not flag:
                ret += 67108863 # 2 ^ 26 - 1
        else:
            ret += 1 << (ord(c) - ordA)
    return ret

A = convert(a, False)
B = convert(b, False)
C = convert(c, False)
notA = ~convert(a, True)
notB = ~convert(b, True)
notC = ~convert(c, True)

La = len(a)
Lb = len(b)
Lc = len(c)
for _ in range(La):
    B <<= 26
    B += 67108863
    notB <<= 26
    notB += 67108863
B <<= 26
B += 67108863
notB <<= 26
notB += 67108863
ans = float('inf')
for bi in range(-Lb, La):
    if bi + Lb < La:
        B >>= 26
        notB >>= 26
    else:
        A <<= 26
        A += 67108863
        notA <<= 26
        notA += 67108863
    tA = A
    tB = B
    tC = C
    tnotA = notA
    tnotB = notB
    tnotC = notC
    bii = min(bi, 0)
    bii2 = max(La, bi+Lb)
    for _ in range(-bii + La):
        tC <<= 26
        tC += 67108863
        tnotC <<= 26
        tnotC += 67108863
    tC <<= 26
    tC += 67108863
    tnotC <<= 26
    tnotC += 67108863
    for ci in range(bii - Lc, bii2):
        if ci + Lc < bii2:
            tC >>= 26
            tnotC >>= 26
        else:
            tA <<= 26
            tA += 67108863
            tnotA <<= 26
            tnotA += 67108863
            tB <<= 26
            tB <<= 26
            tnotB += 67108863
            tnotB += 67108863
        tmp = tA & tB & tC
        if tnotA | tmp == 0 and tnotB | tmp == 0 and tnotC | tmp == 0:
            tmp2 = -min(0, bi, ci) + max(La, bi+Lb, ci+Lc)
            ans = ans if ans < tmp2 else tmp2
print(ans)

Submission status: Wrong Answer

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

L = [A, B, C]


def calc_two(A, B):
    for i in range(len(A)):
        if i >= len(B):
            return A+B
        if all(a == b or a == "?" or b == "?" for a, b in zip(A[i:], B[:len(B)-i])):
            return A+B[len(B)-i:]
    return A+B


def calc_cnt(A, B, C):
    ret = calc_two(A, B)
    ret = calc_two(ret, C)
    return ret


ans = 10**5
for i in range(3):
    for j in range(3):
        if i == j:
            continue
        for k in range(3):
            if i == k or j == k:
                continue
            #print(calc_cnt(L[i], L[j], L[k]))
            ans = min(ans, len(calc_cnt(L[i], L[j], L[k])))
print(ans)

Submission status: Wrong Answer

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

ans = len(A) + len(B) + len(C)

def merge(X, Y):
  ret = []
  for i in range(len(X)):
    s = X[:i]
    for x, y in zip(X[i:], Y):
      if x != '?' and y != '?' and x != y:
        break
      else:
        s += x if x != '?' else y
    else:
      ret.append(s + Y[len(X)-i:])
  return ret

for D in merge(A, B) + merge(B, A):
  for E in merge(D, C) + merge(C, D):
    ans = min(ans, len(E))

for D in merge(A, C) + merge(C, A):
  for E in merge(D, B) + merge(B, D):
    ans = min(ans, len(E))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def concat(x,y):
    len_x = len(x)
    len_y = len(y)
    for i in range(len_x+1):
        z = x[:i]
        ng = False
        for j in range(len_y):
            # log(x,y,i,j)
            if i+j >= len_x:
                z += y[j:]
                break
            elif x[i+j]=="?" or y[j]=="?" or x[i+j]==y[j]:
                if x[i+j]=="?" and y[j]=="?":
                    z += "?"
                else:
                    z += x[i+j] if x[i+j] != "?" else y[j]
            else:
                ng = True
                break
        if not ng:
            # log(x,y,z+x[i+j+1:])
            return z+x[i+j+1:]
    log("XXX")

def solve(x,y,z):
    return min(len(concat(concat(x,y), z)), len(concat(x, concat(y,z))))

print(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)
))

Submission status: Wrong Answer

Solution code:

def same(x: str, y: str):
    for a, b in zip(x, y):
        if a == '?' or b == '?':
            continue
        if a != b:
            return False
    return True


def main():
    a = input()
    b = input()
    c = input()
    length = len(a)
    # AB
    overlap_ab = 0
    for i in range(length):
        if same(a[i:], b[:i]):
            overlap_ab = length - i
            break
    # BC
    overlap_bc = 0
    for i in range(length):
        if same(b[i:], c[:i]):
            overlap_bc = length - i
            break
    # CA
    overlap_ca = 0
    for i in range(length):
        if same(c[i:], a[:i]):
            overlap_ca = length - i
            break
    # BA
    overlap_ba = 0
    for i in range(length):
        if same(b[i:], a[:i]):
            overlap_ba = length - i
            break
    # CB
    overlap_cb = 0
    for i in range(length):
        if same(c[i:], b[:i]):
            overlap_cb = length - i
            break
    # AC
    overlap_ac = 0
    for i in range(length):
        if same(a[i:], c[:i]):
            overlap_ac = length - i
            break

    top1, top2 = list(sorted([overlap_ab, overlap_bc, overlap_ca, overlap_ba, overlap_cb, overlap_ac]))[-2:]
    print(length * 3 - top1 - top2)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
def input():
	return sys.stdin.readline()[:-1]

def same(A, B):
	L = len(A)
	for l in range(L):
		if A[l] == B[l] or A[l] == "?" or B[l] == "?":
			pass
		else:
			return False
	return True

t = [input() for _ in range(3)]

def In(x, y):
	if len(x) > len(y):
		return False
	else:
		for i in range(len(y)-len(x)+1):
			if same(x, y[i:i+len(x)]):
				return True
	return False

ans = sum([len(x) for x in t])
for p in permutations(range(3)):
	a, b, c = t[p[0]], t[p[1]], t[p[2]]
	la, lb, lc = len(a), len(b), len(c)
	if In(a, b):
		d = b
	elif In(b, a):
		d = a
	for i in range(min(la, lb), 0, -1):
		if same(a[la-i:], b[:i]):
			d = a + b[i:]
			break
	else:
		d = a + b

	ld = len(d)
	if In(d, c):
		e = c
	elif In(c, d):
		e = d
	for i in range(min(ld, lc), 0, -1):
		if same(d[ld-i:], c[:i]):
			e = d + c[i:]
			break
	else:
		e = d + c
	ans = min(ans, len(e))

print(ans)

Submission status: Wrong Answer

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

def check(left, right):
    for i in range(len(left)):
        if(left[i] != "?" and right[i] != "?" and left[i] != right[i]):
            return False
    return True

def merge(left, right):
    ans = ""
    for i in range(len(left)):
        if(left[i] == "?"):
            ans += right[i]
        else:
            ans += left[i]
    return ans

def connect(left, right):
    rev = False
    if(len(left) < len(right)):
        rev = True
        tmp = left
        left = right
        right = tmp
    for i in range(len(left)):
        last_index = min(len(left), i + len(right))
        if(check(left[i:last_index], right[:last_index]) == True):
            if(last_index < len(left)):
                return left
            else:
                return left[:i] + merge(left[i:last_index], right[:last_index-i]) + right[last_index-i:]
    if(rev):
        return right + left
    else:
        return left + right    

ansList = []
ansList.append(connect(a, connect(b, c)))
ansList.append(connect(a, connect(c, b)))
ansList.append(connect(b, connect(a, c)))
ansList.append(connect(b, connect(c, a)))
ansList.append(connect(c, connect(a, b)))
ansList.append(connect(c, connect(b, a)))

minAns = 99999
for ans in ansList:
    minAns = min(minAns, len(ans))
print(minAns)

Submission status: Wrong Answer

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


def check(x, y):
    r = ""
    for i, j in zip(x, y):
        if i == j:
            r += i
            continue
        if i == "?" and j == "?":
            r += "?"
            continue
        if j == "?":
            r += i
            continue
        if i == "?":
            r += j
        return ""
    return r


# x, yの順で結合する
def unite(x, y):
    cnt = min(len(x), len(y))
    while True:
        r = x[-cnt:]
        s = y[:cnt]
        if check(r, s):
            return x[:-cnt] + check(r, s) + y[cnt:]
        else:
            cnt -= 1
        if cnt == 0:
            break
    return x + y


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

Submission status: Wrong Answer

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

def check_two(x, y):
    keyi = []
    for i in range(len(x)):
        ok = True
        now = []
        for j in range(min(len(x[i:]),len(y))):
            if x[i + j] != y[j] and x[i + j] != "?" and y[j] != "?":
                ok = False
                now = []
                break
            else:
                if x[i + j] == "?":
                    now.append(y[j])
                else:
                    now.append(x[i + j])
        if ok == True:
            keyi.append(x[:i] + "".join(now) + y[j + 1:] + x[i + len(y):])
    return keyi

keyikeyi = []
for i in (check_two(a,b)):
    keyikeyi.extend(check_two(i, c))
for i in (check_two(a,c)):
    keyikeyi.extend(check_two(i, b))
for i in (check_two(b,c)):
    keyikeyi.extend(check_two(i, a))
for i in (check_two(b,a)):
    keyikeyi.extend(check_two(i, c))
for i in (check_two(c,a)):
    keyikeyi.extend(check_two(i, b))
for i in (check_two(c,b)):
    keyikeyi.extend(check_two(i, a))

miner = 10000000
for i in keyikeyi:
    miner = min(miner, len(i))

print(miner)


# s1 = check_two(check_two(a, b),c)
# s2 = check_two(check_two(a, c),b)
# s3 = check_two(check_two(b, a),c)
# s4 = check_two(check_two(b, c),a)
# s5 = check_two(check_two(c, b),a)
# s6 = check_two(check_two(c, a),b)
# print(s1,s2,s3,s4,s5,s6)
# print(min(len(s1),len(s2),len(s3),len(s4),len(s5),len(s6)))

Submission status: Wrong Answer

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


def AAA(a,b):
    cntmax = 0
    b = 'A'*(len(a)-1) + b + 'A'*(len(a)-1)
    for i in range(len(b)-len(a)+1):
        cnt = 0
        for j in range(len(a)):
            if b[i+j] == a[j] or b[i+j] == '?' or a[j] == '?':
                cnt = cnt + 1
        if cntmax < cnt:
            cntmax = cnt
    return cntmax

q1 = AAA(a,b)
q2 = AAA(b,c)
q3 = AAA(c,a)

print(len(a)+len(b)+len(c)-max(q1+q2,q2+q3,q3+q1))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def make_index(A, B):
    I = []
    for i in range(len(A)):
        for j in range(min(len(B), len(A) - i)):
            if A[i + j] == "?":
                continue

            if B[j] == "?":
                continue

            if A[i + j] != B[j]:
                break
        else:
            I.append(i)
        
    I.append(len(A))
    return I


def check(AB, BC, AC, len_c):
    import bisect

    res = 10 ** 20
    for i in AB:
        for j in BC:
            if i + j >= AB[-1]:
                res = min(res, i + max(j + len_c, BC[-1]))
                continue

            t = bisect.bisect_left(AC, i + j) 
            if AC[t] != i + j:
                continue
            res = min(res, max(AB[-1], i + BC[-1], i + j + len_c))
    return res


def main():
    A = input().strip()
    B = input().strip()
    C = input().strip()
    AB = make_index(A, B)
    BA = make_index(B, A)
    BC = make_index(B, C)
    CB = make_index(C, B)
    CA = make_index(C, A)
    AC = make_index(A, C)

    res = min(
        check(AB, BC, AC, len(C)), 
        check(BA, AC, BC, len(C)), 
        check(BC, CA, BA, len(A)), 
        check(CB, BA, CA, len(A)), 
        check(CA, AB, CB, len(B)), 
        check(AC, CB, AB, len(B))
        )
    print(max(res, 1))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    a = input()
    na = len(a)

    b = input()
    nb = len(b)

    c = input()
    nc = len(c)

    def intersect(p, q):
        if not p or not q:
            return 0

        lp = len(p)
        lq = len(q)

        head = q[0]
        cand = []
        for pi in range(lp):
            if head == '?' or p[pi] == '?' or p[pi] == head:
                cand.append((pi, lp - pi))

        for pi, ans in cand:
            if ans > lq: continue
            for pc, qc in zip(p[pi:], q):
                if not (pc == qc or pc == '?' or qc == '?'):
                    break
            else:
                return ans

        return 0

    def has(p, q):
        """pの中にq入ってる"""
        if not p or not q:
            return True

        lp = len(p)
        lq = len(q)

        head = q[0]
        cand = []
        for pi in range(lp):
            if head == '?' or p[pi] == '?' or p[pi] == head:
                if pi + lq - 1 < lp:
                    cand.append(pi)

        for pi in cand:
            for pc, qc in zip(p[pi:], q):
                if not (pc == qc or pc == '?' or qc == '?'):
                    break
            else:
                return True

        return False

    a_has_b = has(a, b)
    a_has_c = has(a, c)
    b_has_a = has(b, a)
    b_has_c = has(b, c)
    c_has_a = has(c, a)
    c_has_b = has(c, b)

    at_bh = intersect(a, b)
    bt_ch = intersect(b, c)
    at_ch = intersect(a, c)
    ct_bh = intersect(c, b)
    bt_ah = intersect(b, a)
    ct_ah = intersect(c, a)

    ret = na + nb + nc

    def joint(p, q, num):
        ret = ''
        for pc, qc in zip(p[-num:], q[:num]):
            if pc == qc:
                ret += pc
            elif pc == '?':
                ret += qc
            elif qc == '?':
                ret += pc
        return ret

    k = intersect(a, b)
    ab = a[:-k] + joint(a, b, k) + b[k:]

    k = intersect(b, c)
    bc = b[:-k] + joint(b, c, k) + c[k:]

    k = intersect(a, c)
    ac = a[:-k] + joint(a, c, k) + c[k:]

    k = intersect(c, b)
    cb = c[:-k] + joint(c, b, k) + b[k:]

    k = intersect(b, a)
    ba = b[:-k] + joint(b, a, k) + a[k:]

    k = intersect(c, a)
    ca = c[:-k] + joint(c, a, k) + a[k:]

    ret = na + nb + nc

    ret = min(ret, len(ab) + len(c) - intersect(ab, c))
    ret = min(ret, len(ac) + len(b) - intersect(ac, b))
    ret = min(ret, len(ba) + len(c) - intersect(ba, c))
    ret = min(ret, len(bc) + len(a) - intersect(bc, a))
    ret = min(ret, len(ca) + len(b) - intersect(ca, b))
    ret = min(ret, len(cb) + len(a) - intersect(cb, a))

    if a_has_b:
        ret = min(ret, na + nc - at_ch)
        x1 = na + nc - at_ch
        ret = min(ret, na + nc - ct_ah)
        x2 = na + nc - ct_ah

    if a_has_c:
        ret = min(ret, na + nb - at_bh)
        x3 = na + nb - at_bh
        ret = min(ret, na + nb - bt_ah)
        x4 = na + nb - bt_ah

    if b_has_a:
        ret = min(ret, nb + nc - bt_ch)
        x5 = nb + nc - bt_ch
        ret = min(ret, nb + nc - ct_bh)
        x6 = nb + nc - ct_bh

    if b_has_c:
        ret = min(ret, na + nb - bt_ah)
        x7 = na + nb - bt_ah
        ret = min(ret, na + nb - at_bh)
        x8 = na + nb - at_bh

    if c_has_a:
        ret = min(ret, nb + nc - bt_ch)
        x9 = nb + nc - bt_ch
        ret = min(ret, nb + nc - ct_bh)
        x10 = nb + nc - ct_bh

    if c_has_b:
        ret = min(ret, na + nc - ct_ah)
        x11 = na + nc - ct_ah
        ret = min(ret, na + nc - at_ch)
        x12 = na + nc - at_ch

    if a_has_b and b_has_c:
        ret = min(ret, max(na, nb, nc))

    if a_has_c and c_has_b:
        ret = min(ret, max(na, nb, nc))

    if b_has_a and a_has_c:
        ret = min(ret, max(na, nb, nc))

    if b_has_c and c_has_a:
        ret = min(ret, max(na, nb, nc))

    if c_has_a and a_has_b:
        ret = min(ret, max(na, nb, nc))

    if c_has_b and b_has_a:
        ret = min(ret, max(na, nb, nc))

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

#     res = intersect('abc', 1, '', 1)
#     print(res)

Submission status: Wrong Answer

Solution code:
def inner(a,b,la,lb):
  for i in range(lb-la+1):
    tmp=''
    for j in range(la):
      if a[j]=='?' or a[j]==b[i+j]:
        tmp+=b[i+j]
        continue
      elif b[i+j]=='?':
        tmp+=a[j]
        continue
      else:
        break
    else:
      return True
  return False

def head(a,b,la):
  for i in range(la-1,-1,-1):
    tmp=''
    for j in range(i):
      if a[j]=='?' or a[j]==b[-(i-j)]:
        tmp+=b[-(i-j)]
        continue
      elif b[-(i-j)]=='?':
        tmp+=a[j]
        continue
      else:
        break
    else:
      return b+a[i:]

def tail(a,b,la):
  for i in range(la-1,-1,-1):
    tmp=''
    for j in range(i):
      if a[-(i-j)]=='?' or a[-(i-j)]==b[j]:
        tmp+=b[j]
        continue
      elif b[j]=='?':
        tmp+=a[-(i-j)]
        continue
      else:
        break
    else:
      return a+b[i:]
      break

a=input()
la=len(a)
b=input()
lb=len(b)
c=input()
lc=len(c)
arr=[[a,la],[b,lb],[c,lc]]
arr=sorted(arr,key=lambda x:x[1])
a,la=arr[0]
b,lb=arr[1]
c,lc=arr[2]
tmp1=head(a,c,la)
tmp2=tail(a,c,la)
ans1=min(len(head(b,tmp1,lb)),len(tail(b,tmp1,lb)))
if inner(b,tmp1,lb,len(tmp1)):
  ans1=min(ans1,len(tmp1))
ans2=min(len(head(b,tmp2,lb)),len(tail(b,tmp2,lb)))
if inner(b,tmp2,lb,len(tmp2)):
  ans2=min(ans2,len(tmp2))
ans3=10**18
if inner(a,c,la,lc):
  ans3=min(len(head(b,c,lb)),len(tail(b,c,lb)))
  if inner(b,c,lb,lc):
    ans3=min(ans3,lc)
print(min(ans1,ans2,ans3))

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import *
import sys
#input = sys.stdin.readline


#N=int(input())

#A=list(map(int,input().split()))
#XY=[list(map(int,input().split())) for i in range(N)]

D=[list(input()),list(input()),list(input())]

value=10**9
for a,b,c in permutations([0,1,2]):
    #print(a,b,c)

    a=copy.copy(D[a])
    b=copy.copy(D[b])
    c=copy.copy(D[c])

    blst=[]
    for i in range(len(b)):
        if b[i]=="?" or c[0]=="?" or b[i]==c[0]:
            for m in range(min(len(b)-i-1,len(c)-1)):
                if b[i+1+m]=="?" or c[m+1]=="?" or b[i+1+m]==c[m+1]:
                    pass
                else:
                    break
            else:
                blst.append(b[:i]+c)

    if not blst:
        blst.append(b+c)

    b=sorted(blst,key=lambda x:len(x))[0]


    for i in range(len(a)):
        if a[i]=="?" or b[0]=="?" or a[i]==b[0]:
            for m in range(min(len(a)-i-1,len(b)-1)):
                if a[i+1+m]=="?" or b[m+1]=="?" or a[i+1+m]==b[m+1]:
                    pass
                else:
                    break
            else:
                value=min(value,len(a[:i])+len(b))
                break
print(value)
#N=int(input())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def main():
    a,b,c=input(),input(),input()
    def get_co(s1, s2):
        if len(s1) < len(s2):
            s1, s2 = s2, s1
        s = [s1+s2, s2+s1]
        t = []
        for s2off in range(-len(s2)+1, len(s1)):
            left = max(0, s2off)
            right = min(s2off+len(s2), len(s1))
            if right-left > len(s[0]):
                continue
            t.clear()
            for i in range(left, right):
                if s1[i] == '?':
                    t.append(s2[i-s2off])
                elif s2[i-s2off] == '?':
                    t.append(s1[i])
                elif s1[i] == s2[i-s2off]:
                    t.append(s1[i])
                else:
                    t.clear()
                    break
            if not t:
                continue
            ts = s2[:abs(s2off)] if s2off<0 else s1[:s2off]
            ts += ''.join(t)
            if s2off<0:
                ts += s2[:abs(s2off)]
            elif right < len(s1):
                ts += s1[right:]
            else:
                ts += s2[s2off+len(s2)-len(s1):]
            if len(ts) < len(s[0]):
                s.clear()
            s.append(ts)
        return s
    cands = get_co(a, b)
    ans = 10**100
    for cand in cands:
        ans = min(ans, len(get_co(cand, c)[0]))
    print(ans)



main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

N = len(A)


def compare(x, y):
    #print("COMPARE:", x, y)
    if not (x and y):
        return False
    for a, b in zip(x, y):
        if a == b or a == '?' or b == '?':
            continue
        else:
            # print("False")
            return False
    # print("True")
    return True


def getNewStr(X, Y):
    ans = []
    for _ in range(2):
        X, Y = Y, X
        for i in range(N, -1, -1):
            if compare(X[-i:], Y[:i]):
                ans.append(X + Y[i:])
                break

    return ans


def getMaxStr(X, Y):
    #print("getMAX", X, Y)
    n = len(X)
    m = len(Y)
    ans = 0
    for i in range(n, -1, -1):
        if m < i:
            if compare(X[i - m:i], Y):
                ans = max(ans, m)
                break
        else:
            if compare(X[:i], Y[-i:]):
                ans = max(ans, i)
                break

    for i in range(n, -1, -1):
        if m < i:
            if compare(X[-i: -i + m], Y):
                ans = max(ans, m)
                break
        else:
            if compare(X[-i:], Y[i:]):
                ans = max(ans, i)
                break

    return ans


# まずAとBを比較
# 先頭から

ans = N * 3
for _ in range(3):
    A, B, C = C, A, B

    rs = getNewStr(A, B)

    #print("rs", rs)
    if not rs:
        continue

    for r in rs:
        m = getMaxStr(r, C)
        #print("r", r, "m", m)
        if m == 0:
            ans = min(ans, len(r)+len(C))
        elif m == len(C):
            ans = min(ans, len(r))
        else:
            ans = min(ans, len(r)+N-m)

print(ans)

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):
    def f(a, b):
        if len(a) < len(b):
            a, b = b, a
        for i in range(len(a)):
            for j in range(0, min(len(a)-i, len(b))):
                if a[i+j] == '?':
                    continue
                if b[j] == '?':
                    continue
                if a[i+j] == b[j]:
                    continue
                break
            else:
                return a[:i] + b

        return a + b

    ans = len(A) + len(B) + len(C)
    for a, b, c in permutations([A, B, C]):
        ab = f(a, b)
        s = f(ab, c)
        ans = min(ans, len(s))

    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()

ans = len(A) + len(B) + len(C)

def merge(X, Y):
  ret = []
  for i in range(len(X)):
    s = X[:i]
    for x, y in zip(X[i:], Y):
      if x != '?' and y != '?' and x != y:
        break
      else:
        s += x if x != '?' else y
    else:
      ret.append(s + Y[len(X)-i:])
  return ret

for D in merge(A, B) + merge(B, A):
  for E in merge(D, C) + merge(C, D):
    ans = min(ans, len(E))

for D in merge(A, C) + merge(C, A):
  for E in merge(D, B) + merge(B, D):
    ans = min(ans, len(E))

for D in merge(B, C) + merge(C, B):
  for E in merge(D, A) + merge(A, D):
    ans = min(ans, len(E))

print(ans)

Submission status: Wrong Answer

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

def common(s1, s2):
	l1 = len(s1)
	l2 = len(s2)
	memo = [[0 for i in range(l1+2)] for j in range(l2+2)]

	for idx1,w1 in enumerate(s1):
		for idx2,w2 in enumerate(s2):
			if w1==w2 or w1=='?'or w2=='?':
				memo[idx2+1][idx1+1] = memo[idx2][idx1] + 1

	return memo
m1 = 0
m2 = 0
m3 = 0
for l in common(a,b):
	if max(l)>m1:
		m1 = max(l)
for l in common(a,c):
	if max(l)>m2:
		m2 = max(l)
for l in common(b,c):
	if max(l)>m3:
		m3 = max(l)
ans=len(a)+len(b)+len(c)-m1-m2-m3+min([m1,m2,m3])

print(ans)

Submission status: Wrong Answer

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


def check(S, T):
    """
    S,Tの順に結合する
    """
    Ns = len(S)

    for i, t in enumerate(T):
        if t != "?":
            break
    T = T[i:]
    Nt = len(T)
    match = 0

    for i, s in enumerate(S):
        if s == T[0] or s == "?" or T[0] == "?":
            x = i
            y = 0
            while x < Ns and y < Nt:
                if S[x] == "?" or T[y] == "?" or S[x] == T[y]:
                    x += 1
                    y += 1
                    continue
                else:
                    break
            else:
                match = max(match, y)
    suffix = T[match:]
    return S + suffix


abc = check(check(A, B), C)
acb = check(check(A, C), B)
bac = check(check(B, A), C)
bca = check(check(B, C), A)
cab = check(check(C, A), B)
cba = check(check(C, B), A)
# print(abc)
# print(acb)
# print(bac)
# print(bca)
# print(cab)
# print(cba)

ans = min(len(x) for x in [abc, acb, bac, bca, cab, cba])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools

S = [input() for _ in range(3)]

def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = (word[i] == word[j] or word[i]=='?' or word[j]=='?')

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table
 
def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0

    while i < len(text) and p < len(word):
        if (text[i] == word[p] or text[i]=='?' or word[p]=='?'):
            i += 1
            p += 1
        elif p == 0:
            i += 1
        else:
            p = table[p]
            
    return p
        
 




L = len(S[0])+len(S[1])+len(S[2])
ans = 10**9+10
for order in itertools.permutations([0,1,2]):
    res = L
    minus = 0
    for i in range(2):
        minus += kmp_search(S[order[i]],S[order[i+1]])
    ans = min(ans,res-minus)
print(ans)