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:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
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 += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
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
"""
# AC
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
"""
# TLE?
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)
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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: Accepted

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
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 += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
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
"""
# AC
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
"""
# TLE?
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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: Accepted

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
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 += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
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
"""
# AC
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
"""
# TLE?
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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: Accepted

Solution code:
"""
検証: https://twitter.com/neterukun_cd/status/1283020759942619139
"""
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 += [63] * (MAX_N - len_a + 10)
b += [63] * (MAX_N - len_b + 10)
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
"""
# AC
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)
"""
# TLE?
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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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: Accepted

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 + [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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

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

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 + [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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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)

for len1 in range(MAX_N + 1):
    for len2 in range(MAX_N + 1):
        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: Accepted

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

def calc(s1, s2, s3):
    f12 = [True]*2001
    f23 = [True]*2001
    f13 = [True]*4001
    
    for i in range(2001):
        for j in range(len(s2)):
            if i+j>=len(s1):
                break
            
            if s1[i+j]!='?' and s2[j]!='?' and s1[i+j]!=s2[j]:
                f12[i] = False
                break
    
    for i in range(2001):
        for j in range(len(s3)):
            if i+j>=len(s2):
                break
            
            if s2[i+j]!='?' and s3[j]!='?' and s2[i+j]!=s3[j]:
                f23[i] = False
                break
    
    for i in range(4001):
        for j in range(len(s3)):
            if i+j>=len(s1):
                break
            
            if s1[i+j]!='?' and s3[j]!='?' and s1[i+j]!=s3[j]:
                f13[i] = False
                break
    
    res = 1000000
    
    for i in range(2001):
        for j in range(2001):
            if f12[i] and f23[j] and f13[i+j]:
                res = min(res, max(len(s1), i+len(s2), i+j+len(s3)))
    
    return res

a = input()[:-1]
b = input()[:-1]
c = input()[:-1]
ans = 1000000
ans = min(ans, calc(a, b, c))
ans = min(ans, calc(a, c, b))
ans = min(ans, calc(b, a, c))
ans = min(ans, calc(b, c, a))
ans = min(ans, calc(c, a, b))
ans = min(ans, calc(c, b, a))
print(ans)

Submission status: Accepted

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): # 2つの文字列とその相対的位置に対して合わさるかチェック
    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

#ab,ac,bcに対して計算する
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): #BとCが離れすぎている場合を除く
                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: Accepted

Solution code:
def main():
  ab=[1]*100000
  bc=[1]*100000
  ac=[1]*100000
  a=input()
  b=input()
  c=input()
  A,B,C=len(a),len(b),len(c)
  match=lambda x,y:x=="?" or y=="?" or x==y
  for i in range(A):
    for j in range(B):
      if not match(a[i],b[j]):ab[i-j+50000]=0
  for i in range(A):
    for j in range(C):
      if not match(a[i],c[j]):ac[i-j+50000]=0
  for i in range(B):
    for j in range(C):
      if not match(b[i],c[j]):bc[i-j+50000]=0
  ans=10**20
  for i in range(-4000,4001):
    for j in range(-4000,4001):
      if ab[i+50000]+ac[j+50000]+bc[j-i+50000]==3:
        ans=min(ans,max(A,B+i,C+j)-min(0,i,j))
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
ab=[1]*100000
bc=[1]*100000
ac=[1]*100000
a=input()
b=input()
c=input()
A,B,C=len(a),len(b),len(c)
match=lambda x,y:x=="?" or y=="?" or x==y
for i in range(A):
  for j in range(B):
    if not match(a[i],b[j]):ab[i-j+50000]=0
for i in range(A):
  for j in range(C):
    if not match(a[i],c[j]):ac[i-j+50000]=0
for i in range(B):
  for j in range(C):
    if not match(b[i],c[j]):bc[i-j+50000]=0
ans=10**20
for i in range(-4000,4001):
  for j in range(-4000,4001):
    if ab[i+50000]+ac[j+50000]+bc[j-i+50000]==3:
      ans=min(ans,max(A,B+i,C+j)-min(0,i,j))
print(ans)

Submission status: Accepted

Solution code:
# パナソニック2020E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



a,b,c = [input() for _ in range(3)]
la, lb, lc = len(a), len(b), len(c)

def ok(c1,c2):
    return True if c1==c2 or c1=="?" or c2=="?" else False
def sub(s,t,gap=0):
    # tを固定したとき、
    # sの開始位置座標としてありえるもののset
    S = set(list(range(-len(s)-gap, -len(s)+1)) + list(range(len(t), len(t)+gap+1)))
    i1 = min(len(s), len(t))
    i2 = max(len(s), len(t))
    i3 = len(s)+len(t)
    for i in range(1,i1+1):
        if all((ok(s[-i+ii], t[ii])) for ii in range(i)):
            S.add(i-len(s))
    for i in range(i1, i2):
        if len(s)<len(t) and all((ok(s[ii], t[ii+i-i1]) for ii in range(i1))):
            S.add(i-len(s))
        elif len(t)<len(s) and all(ok(s[i2-i+ii], t[ii]) for ii in range(i1)):
            S.add(i-len(s))
    for i in range(i2, i3):
        if all((ok(s[ii], t[i-i3+ii]) for ii in range(i3-i))):
            S.add(i-len(s))
    return S

ab = sub(a,b, lc)
bc = sub(c,b, la)
ac = sub(a,c, lb)
ans = 10**9
import itertools
for ii, jj in itertools.product(ab, bc):
    if ii - jj in ac:
        val = max(lb, ii+la, jj+lc) - min(0, ii, jj)
        ans = min(ans, val)
print(ans)

Submission status: Accepted

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

A = list(map(lambda x:ord(x)-63, readline().strip()))
B = list(map(lambda x:ord(x)-63, readline().strip()))
C = list(map(lambda x:ord(x)-63, readline().strip()))

LA = len(A)
LB = len(B)
LC = len(C)
geta = 4002

tAB = [True]*(2*geta + 4)
for i in range(-geta//2, geta//2+1):
    for j in range(LB):
        if 0 <= j+i < LA and A[i+j] and B[j] and A[i+j] != B[j]:
            tAB[i] = False
            break

tAC = [True]*(2*geta + 4)
for i in range(-geta//2, geta//2+1):
    for j in range(LC):
        if 0 <= j+i < LA and A[i+j] and C[j] and A[i+j] != C[j]:
            tAC[i] = False
            break


tBC = [True]*(2*geta + 4)
for i in range(-geta, geta+1):
    for j in range(LC):
        if 0 <= j+i < LB and B[i+j] and C[j] and B[i+j] != C[j]:
            tBC[i] = False
            break

ans = 3*geta
for ib in range(-geta, geta+1):
    if tAB[ib]:
        for ic in range(min(0, ib)-LC, 1+max(LA-1, ib+LB-1)):
            if tAC[ic]:
                if -geta <= ic-ib <= geta and not tBC[ic-ib]:
                    continue
                l = min(0, ib, ic)
                r = max(LA-1, ib+LB-1, ic+LC-1)
                ans = min(ans, r-l+1)
print(ans)

Submission status: Accepted

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

    X=[a,b,c]
    LEN=[len(a),len(b),len(c)]

    MF=[[[1]*2001 for j in range(3)] for i in range(3)]

    for i in range(3):
        for j in range(3):
            if i==j:
                continue
            for k in range(2001):
                for l in range(LEN[j]):
                    if k+l>=LEN[i]:
                        break
                    if X[i][k+l]!="?" and X[j][l]!="?" and X[i][k+l]!=X[j][l]:
                        MF[i][j][k]=0
                        break

    ANS=1000000
    for i in range(3):
        for j in range(3):
            if i==j:
                continue
            for k in range(2001):
                if MF[i][j][k]==1:
                    for l in range(2001):
                        if ANS<=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l):
                            break
                        if MF[j][3-i-j][l]==1 and (k+l>2000 or MF[i][3-i-j][k+l]==1):
                            ANS=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l)

    print(ANS)
main()

Submission status: Accepted

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

X=[a,b,c]
LEN=[len(a),len(b),len(c)]

MF=[[[1]*2001 for j in range(3)] for i in range(3)]

for i in range(3):
    for j in range(3):
        if i==j:
            continue
        for k in range(2001):
            for l in range(LEN[j]):
                if k+l>=LEN[i]:
                    break
                if X[i][k+l]!="?" and X[j][l]!="?" and X[i][k+l]!=X[j][l]:
                    MF[i][j][k]=0
                    break

ANS=1000000
for i in range(3):
    for j in range(3):
        if i==j:
            continue
        for k in range(2001):
            if MF[i][j][k]==1:
                for l in range(2001):
                    if ANS<=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l):
                        break
                    if MF[j][3-i-j][l]==1 and (k+l>2000 or MF[i][3-i-j][k+l]==1):
                        ANS=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l)

print(ANS)

Submission status: Accepted

Solution code:
K=4000
R=range
y=min
l=len
A,B,C=[input()for i in R(3)]
def F(a,b):
 Q=[1]*(K*2+1)
 for i in R(-l(b),l(a)):
  for j in R(max(i,0),y(l(a),l(b)+i)):
   if l(set([a[j],b[j-i],'?']))>2:Q[i]=0
 return Q
S=F(A,B)
T=F(A,C)
U=F(B,C)
m=K*3
k=R(-K,K+1)
for p in k:
 if S[p]!=0:
  for q in k:
   if T[q]!=0 and U[q-p]!=0:m=y(m,max(p+l(B),q+l(C),l(A))-y(p,q,0))
print(m)

Submission status: Accepted

Solution code:
K=4000
R=range
y=min
l=len
S=[input()for i in R(3)]
A,B,C=S
a,b,c=[l(i)for i in S]
def F(S,T):
 Q=[1]*(K*2+1)
 for i in R(-l(T),l(S)):
  for j in R(max(i,0),y(l(S),l(T)+i)):
   if l(set([S[j],T[j-i],'?']))>2:Q[i]=0
 return Q
S=F(A,B)
T=F(A,C)
U=F(B,C)
m=K*3
k=R(-K,K+1)
for p in k:
 if S[p]!=0:
  for q in k:
   if T[q]!=0 and U[q-p]!=0:m=y(m,max(p+b,q+c,a)-y(p,q,0))
print(m)

Submission status: Accepted

Solution code:
#!python3

import itertools

import numpy as np


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


def judge_array(x, y):
    l = [None] * 2001
    for i in range(2001):
        s = x[i:]
        t = y[:2001 - i]
        l[i] = np.all(np.where((s == t) | (s == 0) | (t == 0), True, False))
    return l


def main():
    n = [len(a), len(b), len(c)]
    d = {chr(ord('a') + i - 1): i for i in range(1, 27)}
    d['?'] = 0
    abc = np.full((3, 2001), np.zeros(2001))
    for i in range(2000):
        if i < n[0]:
            abc[0][i] = d[a[i]]
        if i < n[1]:
            abc[1][i] = d[b[i]]
        if i < n[2]:
            abc[2][i] = d[c[i]]

    w = [[None] * 3, [None] * 3, [None] * 3]
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            w[i][j] = judge_array(abc[i], abc[j])
    
    l = itertools.permutations([0, 1, 2])
    ans = 6000
    for x, y, z in l:
        xy = w[x][y]
        xz = w[x][z]
        yz = w[y][z]
        for i in range(2001):
            for j in range(2001):
                if xy[i] and yz[j] and xz[min(2000, i + j)]:
                    v = max(n[x], i + n[y], i + j + n[z])
                    ans = min(ans, v)
                    break
    print(ans)


if __name__ == "__main__":
    main()