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: Time Limit Exceeded

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


MAX_N = 2000
a = [ord(char) for char in input()[:-1]]
b = [ord(char) for char in input()[:-1]]
c = [ord(char) for char in input()[:-1]]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [63] * (MAX_N - len_a + 10)
b = b + [63] * (MAX_N - len_b + 10)
c = c + [63] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [ord("?")] * (MAX_N - len_a + 10)
b = b + [ord("?")] * (MAX_N - len_b + 10)
c = c + [ord("?")] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63 and ab[length]:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63 and ba[length]:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63 and bc[length]:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63 and cb[length]:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63 and ca[length]:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63 and ac[length]:
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [ord("?")] * (MAX_N - len_a + 10)
b = b + [ord("?")] * (MAX_N - len_b + 10)
c = c + [ord("?")] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] &= False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] &= False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] &= False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] &= False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] &= False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] &= False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [ord("?")] * (MAX_N - len_a + 10)
b = b + [ord("?")] * (MAX_N - len_b + 10)
c = c + [ord("?")] * (MAX_N - len_c + 10)

ab = [1] * (2 * MAX_N + 10)
ba = [1] * (2 * MAX_N + 10)
bc = [1] * (2 * MAX_N + 10)
cb = [1] * (2 * MAX_N + 10)
ca = [1] * (2 * MAX_N + 10)
ac = [1] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = 0
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = 0

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = 0
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = 0

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = 0
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = 0

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [ord("?")] * (MAX_N - len_a + 10)
b = b + [ord("?")] * (MAX_N - len_b + 10)
c = c + [ord("?")] * (MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break

        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_N = 2000
a = [ord(char) for char in input()]
b = [ord(char) for char in input()]
c = [ord(char) for char in input()]


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + [ord("?")] * (2 * MAX_N - len_a + 10)
b = b + [ord("?")] * (2 * MAX_N - len_b + 10)
c = c + [ord("?")] * (2 * MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break
        if a[i + length] != b[i] and a[i + length] != 63 and b[i] != 63:
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != 63 and a[i] != 63:
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != 63 and c[i] != 63:
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != 63 and b[i] != 63:
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != 63 and a[i] != 63:
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != 63 and c[i] != 63:
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + "?" * (2 * MAX_N - len_a + 10)
b = b + "?" * (2 * MAX_N - len_b + 10)
c = c + "?" * (2 * MAX_N - len_c + 10)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if i + length > MAX_N:
            break
        if a[i + length] != b[i] and a[i + length] != "?" and b[i] != "?":
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != "?" and a[i] != "?":
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != "?" and c[i] != "?":
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != "?" and b[i] != "?":
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != "?" and a[i] != "?":
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != "?" and c[i] != "?":
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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


len_a = len(a)
len_b = len(b)
len_c = len(c)

a = a + "?" * (2 * MAX_N)
b = b + "?" * (2 * MAX_N)
c = c + "?" * (2 * MAX_N)

ab = [True] * (2 * MAX_N + 10)
ba = [True] * (2 * MAX_N + 10)
bc = [True] * (2 * MAX_N + 10)
cb = [True] * (2 * MAX_N + 10)
ca = [True] * (2 * MAX_N + 10)
ac = [True] * (2 * MAX_N + 10)


for length in range(MAX_N + 1):
    for i in range(MAX_N + 1):
        if a[i + length] != b[i] and a[i + length] != "?" and b[i] != "?":
            ab[length] = False
        if b[i + length] != a[i] and b[i + length] != "?" and a[i] != "?":
            ba[length] = False

        if b[i + length] != c[i] and b[i + length] != "?" and c[i] != "?":
            bc[length] = False
        if c[i + length] != b[i] and c[i + length] != "?" and b[i] != "?":
            cb[length] = False

        if c[i + length] != a[i] and c[i + length] != "?" and a[i] != "?":
            ca[length] = False
        if a[i + length] != c[i] and a[i + length] != "?" and c[i] != "?":
            ac[length] = False

ans = MAX_N * 6
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        if ab[len1] and bc[len2] and ac[len1 + len2]:
            tmp = max(len_a, len_b + len1, len_c + len1 + len2)
            ans = min(ans, tmp)
        if ba[len1] and ac[len2] and bc[len1 + len2]:
            tmp = max(len_b, len_a + len1, len_c + len1 + len2)
            ans = min(ans, tmp)

        if bc[len1] and ca[len2] and ba[len1 + len2]:
            tmp = max(len_b, len_c + len1, len_a + len1 + len2)
            ans = min(ans, tmp)
        if cb[len1] and ba[len2] and ca[len1 + len2]:
            tmp = max(len_c, len_b + len1, len_a + len1 + len2)
            ans = min(ans, tmp)

        if ca[len1] and ab[len2] and cb[len1 + len2]:
            tmp = max(len_c, len_a + len1, len_b + len1 + len2)
            ans = min(ans, tmp)
        if ac[len1] and cb[len2] and ab[len1 + len2]:
            tmp = max(len_a, len_c + len1, len_b + len1 + len2)
            ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

aa = len(a)
bb = len(b)
cc = len(c)

lensum = aa + bb + cc # 文字列の長さの最大値
ab = [0]*(lensum+cc+1)
ac = [0]*(lensum+bb+1)
bc = [0]*(lensum+aa+1)

def match(v,w): # 2つの文字を合わせられるかどうかを調べる
    if(v != '?' and w != '?' and v != w):
        return 0
    else:
        return 1

def match2(A,B,k):
    AA = len(A)
    BB = len(B)
    if(k>=AA):
        return 1
    elif(k<-BB):
        return 1
    else:
        flg = 1
        st = max(0,k)
        la = min(AA,BB+k)
        for i in range(st,la):
            if(match(A[i],B[i-k])==0):
                flg = 0
                break
        return flg

for i in range(lensum+cc+1):
    ab[i] = match2(a,b,i-bb-cc)
for i in range(lensum+bb+1):
    ac[i] = match2(a,c,i-bb-cc)
for i in range(lensum+aa+1):
    bc[i] = match2(b,c,i-aa-cc)

def milen(a,b,c):
    minlen = lensum # 文字列の長さの最大値
    for i in range(-bb-cc,aa+cc+1): # iが文字列Bの開始位置
        for j in range(-bb-cc,aa+bb+1): # jが文字列Cの開始位置
            if(ab[i+bb+cc] == 0): 
                continue
            elif(ac[j+bb+cc] == 0):
                continue
            elif(j-i+aa+cc < 0 or j-i+aa+cc >= lensum+aa+1):
                continue  
            elif(bc[j-i+aa+cc] == 0):
                continue   
            else:
                sta = min(0,i,j) #文字列の中で一番左にある開始位置
                en = max(aa,i+bb,j+cc) #文字列の中で一番右にある終了位置
                minlen = min(minlen,en-sta) #更新
    return minlen

print(milen(a,b,c))

Submission status: Time Limit Exceeded

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

def match(v,w):
    if(v != '?' and w != '?' and v != w):
        return 0
    else:
        return 1

def middle(x,y,z):
    X = [x,y,z]
    X.sort()
    return(X[1])


def milen(a,b,c):
    aa = len(a)
    bb = len(b)
    cc = len(c)

    minlen = aa + bb + cc
    s = '?'*(bb+cc) + a + '?'*(bb+cc)
    for i in range(-bb-cc,aa+cc+1):
        t = '?'*(bb+cc+i) + b + '?'*(aa+cc-i)
        for j in range(-bb-cc,aa+bb+1):
            u = '?'*(bb+cc+j) + c + '?'*(aa+bb-j)
            flag = 1
            for k in range(middle(0,i,j)+bb+cc,middle(aa,i+bb,j+cc)+bb+cc):
                if(match(s[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(t[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(s[k],t[k]) == 0):
                    flag = 0
                    break
            if(flag == 1):
                sta = min(0,i,j)
                en = max(aa,i+bb,j+cc)
                minlen = min(minlen,en-sta)
    return minlen

print(milen(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

a = input()[:-1]
b = input()[:-1]
c = input()[:-1]
max_shift = max(len(a),len(b),len(c))*2

ans = float('inf')

for i in range(-max_shift, max_shift):
    for j in range(-max_shift, max_shift):
        start = min(i, j, 0)
        end = max(len(a), i+len(b), j+len(c))
        s = ['?'] * (end - start)
        flg = False

        for idx in range(len(a)):
            s[idx - start] = a[idx]

        for idx in range(len(b)):
            if flg:
                break
            if s[i - start + idx] == '?':
                s[i - start + idx] = b[idx]
            elif (b[idx] == '?') or (s[i - start + idx] == b[idx]):
                pass
            else:
                flg=True

        for idx in range(len(c)):
            if flg:
                break
            if s[j - start + idx] == '?':
                s[j - start + idx] = c[idx]
            elif (c[idx] == '?') or (s[j - start + idx] == c[idx]):
                pass
            else:
                flg=True

        if not flg:
            # print(s)
            ans = min(ans, (end-start))

print(ans)

Submission status: Time Limit Exceeded

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

def match(v,w):
    if(v != '?' and w != '?' and v != w):
        return 0
    else:
        return 1

def middle(x,y,z):
    X = [x,y,z]
    X.sort()
    return(X[1])


def milen(a,b,c):
    aa = len(a)
    bb = len(b)
    cc = len(c)

    minlen = aa + bb + cc
    s = '?'*(bb+cc) + a + '?'*(bb+cc)
    for i in range(-bb,aa+1):
        start = min(0,i)
        end = max(aa,i+bb)
        t = '?'*(bb+cc+i) + b + '?'*(aa+cc-i)
        for j in range(start-cc,end+1):
            sta = min(start,j)
            en = max(end,j+cc)
            u = '?'*(bb+cc+j) + c + '?'*(aa+bb-j)
            flag = 1
            for k in range(middle(0,i,j)+bb+cc,middle(aa,i+bb,j+cc)+bb+cc):
                if(match(s[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(t[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(s[k],t[k]) == 0):
                    flag = 0
                    break
            if(flag == 1):
                minlen = min(minlen,en-sta)
    return minlen

print(min(milen(A,B,C),milen(A,C,B)))

Submission status: Time Limit Exceeded

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

def match(v,w):
    if(v != '?' and w != '?' and v != w):
        return 0
    else:
        return 1


def milen(a,b,c):
    aa = len(a)
    bb = len(b)
    cc = len(c)

    minlen = aa + bb + cc
    s = '?'*(bb+cc) + a + '?'*(bb+cc)
    for i in range(-bb,aa+1):
        start = min(0,i)
        end = max(aa,i+bb)
        t = '?'*(bb+cc+i) + b + '?'*(aa+cc-i)
        for j in range(start-cc,end+1):
            sta = min(start,j)
            en = max(end,j+cc)
            u = '?'*(bb+cc+j) + c + '?'*(aa+bb-j)
            flag = 1
            for k in range(sta+bb+cc,en+bb+cc):
                if(match(s[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(t[k],u[k]) == 0):
                    flag = 0
                    break
                if(match(s[k],t[k]) == 0):
                    flag = 0
                    break
            if(flag == 1):
                minlen = min(minlen,en-sta)
    return minlen

print(min(milen(A,B,C),milen(A,C,B)))

Submission status: Time Limit Exceeded

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

def milen(a,b,c):
    aa = len(a)
    bb = len(b)
    cc = len(c)

    minlen = aa + bb + cc
    s = '?'*(bb+cc) + a + '?'*(bb+cc)
    for i in range(-bb,aa+1):
        start = min(0,i)
        end = max(aa,i+bb)
        t = '?'*(bb+cc+i) + b + '?'*(aa+cc-i)
        for j in range(start-cc,end+1):
            sta = min(start,j)
            en = max(end,j+cc)
            u = '?'*(bb+cc+j) + c + '?'*(aa+bb-j)
            flag = 1
            for k in range(sta+bb+cc,en+bb+cc):
                if(s[k] == '?'):
                    if(t[k] != '?' and u[k] != '?' and t[k] != u[k]):
                        flag = 0
                        break
                elif(t[k] == '?'):
                    if(u[k] != '?' and s[k] != u[k]):
                        flag = 0
                        break
                else:
                    if(s[k] != t[k]):
                        flag = 0
                        break
                    else:
                        if(u[k] != '?' and s[k]!= u[k]):
                            flag = 0
                            break
            if(flag == 1):
                minlen = min(minlen,en-sta)
    return minlen



print(min(milen(A,B,C),milen(A,C,B)))

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()
 
# 文字のマッチング(?はワイルドカード)
def match(a, b):
    return a=="?" or b=="?" or a==b
 
ab = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にBを置けるか?
ac = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にCを置けるか?
bc = [True] * 100000 # Bに対して(i-50000)個左にスライドした位置にCを置けるか?
 
def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False
 
check(a, b, ab)
check(a, c, ac)
check(b, c, bc)
 
len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)
 
ans = len_a + len_b + len_c
 
# i = BをAに対していくつスライドして置くか
for i in range(-2 * len_max, 2 * len_max + 1):
    # j = CをAに対していくつスライドして置くか
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def connection(a, b, la, lb):
    #bがaの左にあるとき
    e = [b+a]
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        dic = {} # 文字変更候補のdict
        for j in range(i): # a[j] を調べる
            if a[j] == '?':
                if b[-i+j] != '?':
                    dic[j] = b[-i+j]
            elif a[j] != b[-i+j] and b[-i+j] != '?':
                break
            if j == i - 1:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(b[:lb-i] + d)
                f.append(la+lb-i)

    #bがaの右にあるとき
    e.append(a+b)
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        dic = {} # 文字変更候補のdict
        for j in range(1, i+1): # a[-j] を調べる
            if a[-j] == '?':
                if b[i-j] != '?':
                    dic[-j] = b[i-j]
            elif a[-j] != b[i-j] and b[i-j] != '?':
                break
            if j == i:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(d + b[i:])
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # a[i]から重なる
        dic = {}
        for j in range(lb):
            if a[i+j] == '?':
                if b[j] != '?':
                    dic[i+j] = b[j]
            elif a[i+j] != b[j] and b[j] != '?':
                break
            if j == lb - 1:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(d)
                f.append(la)

    return e, f
    #eはaとbを繋げたもののlist、fはその文字数


def connect(a, b, la, lb):
    #bがaの左にあるとき
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        for j in range(i): # a[j] を調べる
            if a[j] != b[-i+j] and b[-i+j] != '?' and a[j] != '?':
                break
            if j == i - 1:
                f.append(la + lb - i)

    #bがaの右にあるとき
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        for j in range(1, i+1): # a[-j] を調べる
            if a[-j] != b[i-j] and b[i-j] != '?' and a[-j] != '?':
                break
            if j == i:
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # a[i]から重なる
        for j in range(lb):
            if a[i+j] != b[j] and b[j] != '?' and a[i+j] != '?':
                break
            if j == lb - 1:
                f.append(la)

    return f
    #fは文字数


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

#最も長い文字列をaにする
if lb > la and lb >= lc:
    a, b = b, a
    la, lb = lb, la
elif lc > la and lc >= lb:
    a, c = c, a
    la, lc = lc, la

wc = [] #Word Count

e, f = connection(a, b, la, lb)

# aとbが離れているとき
for i in range(1, lc): # i = a と b の間隔
    e.append(b + ['?']*i + a)
    e.append(a + ['?']*i + b)
    f.append(lb + i + la)
    f.append(la + i + lb)

for i in range(len(e)):
    wc += connect(e[i], c, f[i], lc)

print(min(wc))