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:
R=range
K=4000
S=[input()for i in R(3)]
A,B,C=S
a,b,c=[len(i)for i in S]
def F(S,T):
 Q=[1]*(K*2+1)
 for i in R(-len(T),len(S)):
  for j in R(max(i,0),min(len(S),len(T)+i)):
   if len(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
for p in R(-K,K+1):
 if S[p]!=0:
  for q in R(-K,K+1):
   if T[q]!=0 and U[q-p]!=0:
    m=min(m,max(p+b,q+c,a)-min(p,q,0))
print(m)

Submission status: Accepted

Solution code:
R=range
K=4000
S=[input()for i in R(3)]
A,B,C=S
a,b,c=[len(i)for i in S]
def F(S,T):
 Q=[1]*(K*2+1)
 for i in R(-len(T),len(S)):
  for j in R(max(i,0),min(len(S),len(T)+i)):
   if len(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
for p in R(-K,K+1):
 if S[p]!=0:
  for q in R(-K,K+1):
   if T[q]!=0 and U[q-p]!=0:
    m=min(m,max(p+b,q+c,a)-min(p,q,0))
print(m)

Submission status: Accepted

Solution code:
from itertools import permutations

ABC = [input().rstrip(), input().rstrip(), input().rstrip()]

cache = [-1] * (3 * 3)


def canMatchShifted(index1, index2, shift):
    # Whether ABC[index1] can match with ABC[index2] shifted to the right by `shift`
    k = 3 * index1 + index2
    if cache[k] == -1:
        S1 = ABC[index1]
        S2 = ABC[index2]
        temp = [True] * (4001)
        for s in range(len(S1)):
            temp[s] = all(x == y or x == "?" or y == "?" for x, y in zip(S1[s:], S2))
        cache[k] = temp

    return cache[k][shift]


# Try all permutation orders of ABC
best = float("inf")
for a, b, c in permutations(range(3)):
    A = ABC[a]
    B = ABC[b]
    C = ABC[c]
    # Match A with `('?' * i) + B`
    for i in range(len(A) + 1):
        if not canMatchShifted(a, b, i):
            continue
        # Match B with `('?' * j) + C`
        # Match A with `('?' * (i + j)) + C`
        # Note that j can be longer than len(B) if B is a short string in the middle of A and C comes after A
        for j in range(2001):
            if canMatchShifted(b, c, j) and canMatchShifted(a, c, i + j):
                l = max(len(A), i + len(B), i + j + len(C))
                best = min(best, l)
print(best)

Submission status: Accepted

Solution code:
from itertools import permutations

ABC = [input().rstrip(), input().rstrip(), input().rstrip()]

cache = [-1] * (3 * 3)


def canMatchShifted(index1, index2, shift):
    # Whether ABC[index1] can match with ABC[index2] shifted to the right by `shift`
    k = 3 * index1 + index2
    if cache[k] == -1:
        S1 = ABC[index1]
        S2 = ABC[index2]
        temp = [True] * (4001)
        for s in range(len(S1)):
            temp[s] = all(x == y or x == "?" or y == "?" for x, y in zip(S1[s:], S2))
        cache[k] = temp

    return cache[k][shift]


# Try all permutation orders of ABC
best = float("inf")
for a, b, c in permutations(range(3)):
    A = ABC[a]
    B = ABC[b]
    C = ABC[c]
    # Match A with `('?' * i) + B`
    for i in range(2001):
        if not canMatchShifted(a, b, i):
            continue
        # Match B with `('?' * j) + C`
        # Match A with `('?' * (i + j)) + C`
        for j in range(2001):
            if canMatchShifted(b, c, j) and canMatchShifted(a, c, i + j):
                l = max(len(A), i + len(B), i + j + len(C))
                best = min(best, l)
print(best)

Submission status: Accepted

Solution code:
import sys
import itertools
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())


def compare(arr1, arr2):
    for x, y in zip(arr1, arr2):
        if x == y or x == '?' or y == '?':
            continue
        return False

    return True


def can_match(x, y):
    return x == '?' or y == '?' or x == y


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


for A, B, C in itertools.permutations([A, B, C]):

    A_to_B = [True] * CONST
    B_to_C = [True] * CONST
    A_to_C = [True] * (CONST * 2)

    lenA = len(A)
    lenB = len(B)
    lenC = len(C)

    for i in range(lenA+1):
        A_to_B[i] = compare(A[i:], B)

    for i in range(lenB + 1):
        B_to_C[i] = compare(B[i:], C)

    for i in range(lenA+1):
        A_to_C[i] = compare(A[i:], C)

    for i in range(CONST):
        for j in range(CONST):
            if A_to_B[i] and B_to_C[j] and A_to_C[i + j]:
                right = max(lenA, i + lenB, i + j + lenC)
                ans = min(ans, right)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/panasonic2020/submissions/10887966

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

# maxtestcase
#a = 'a' * 2000
#b = 'a' * 2000
#c = 'a' * 2000

La = len(a)
Lb = len(b)
Lc = len(c)

def func(a, b):
    ret = set()
    for i in range(-len(b)+1, len(a)):
        ok = True
        for j in range(max(0, i), min(len(a), len(b)+i)):
            if a[j] != '?' and b[j-i] != '?' and a[j] != b[j-i]:
                ok = False
                break
        if ok:
            ret.add(i)
    return ret

L1 = func(a, b)
L2 = func(a, c)
L3 = func(b, c)
L1.add(-Lb)
L1.add(La)
L2.add(-Lc)
L2.add(La)
L3.add(-Lc)
L3.add(Lb)
ans = 10000
for i in L1:
    for j in L2:
        if j - i in L3 or j - i <= -Lc or j - i >= Lb:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    for k in L3:
        j = i + k
        if j >= La or j <= -Lc:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
for j in L2:
    for k in L3:
        i = j - k
        if i >= La or i <= -Lb:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    
print(ans)

Submission status: Accepted

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

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]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            ans = min(ans, right - left)

print(ans)

Submission status: Accepted

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]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            if right - left < ans:
                ans = right - left

print(ans)

Submission status: Accepted

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)

def match(a, b):
    return a=="?" or b=="?" or a==b

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



# aに対して(i-50000)個左にスライドした位置にbを置けるか？
ab = [True] * 100000
ac = [True] * 100000
bc = [True] * 100000

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

log("check end.")

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 = 9999999999999999999999

for i in range(-2 * len_max, 2 * len_max + 1):
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            ans = min(ans, right - left)

print(ans)

Submission status: Accepted

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] != '?' and a[i] != b[j]:
            ab[i-j+8000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and b[i] != c[j]:
            bc[i-j+8000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and a[i] != c[j]:
            ac[i-j+8000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain, permutations, dropwhile
from heapq import merge
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
    if comp_wild(a[i:], b):
      yield i 

@listify
def connectors(a,b):
  for i in range(max(len(a)-len(b)+1, 1), len(a)+1):
    if comp_wild(a[i:], b):
      yield i

class c_int(int):
  def __new__(cls, *args, **kwargs):
    cond = kwargs.pop("cond", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cond = cond
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(*keys):
  keys = sorted(keys, key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = { (i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  con = { (i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if (
        j+len_keys[2] <= i or i+len_keys[2] <= j or
        j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]
      ):
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      ( c_int(
          i+len_keys[z], 
          cond=lambda:(
            (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
            (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
            any(
              (i-j in con[y,z] if i > j else j-i in inc[z,y])
               for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y])
            )
          )
        ) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)
      ),
      ( c_int(
          min( i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p )
        ) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]
      ),
    )
  
  for c in merge(*( candicates(*xyz) for xyz in permutations(range(3), 3) )):
    if c.cond():
      return c
  
  return sum(len_keys)

print(solve(*(input() for i in range(3))))

Submission status: Accepted

Solution code:
def match(x, y):
    """
    １文字x, yが一致するか少なくとも一方が？であればTrueを返す。
    """
    return x == y or x == "?" or y == "?"


def func(a, b, c, la, lb, lc):
    """
    文字列の並びがa->b->cの場合を仮定して考える。
    aに対するb, cの配置が高々2000 * 2000通りあるので、文字列が一致するかの判定はO(1)でしないとTLE。
    これは先にaとb、bとc、aとcに対して文字列の一致を前処理確認しておけばOK <= 思いつかなかったので反省。

    ab[i] = (b[0]をa[i]から重ねたとき、合成文字列は一致するか)
    bc[i] = (c[0]をb[i]から重ねたとき、合成文字列は一致するか)
    ac[i] = (c[0]をa[i]から重ねたとき、合成文字列は一致するか)
    とおく。後ろに[True] * 2000を付け加えているのはaとbがdisjointな場合を考慮するため。
    """
    ab = [True] * (la + 4000)
    bc = [True] * (lb + 4000)
    ac = [True] * (la + 4000)

    for i in range(la):
        for j in range(min(la - i, lb)):
            if not match(a[i + j], b[j]):
                ab[i] = False
                break

    for i in range(lb):
        for j in range(min(lb - i, lc)):
            if not match(b[i + j], c[j]):
                bc[i] = False
                break

    for i in range(la):
        for j in range(min(la - i, lc)):
            if not match(a[i + j], c[j]):
                ac[i] = False
                break
    #print("ab={}".format(ab[:la]))
    #print("bc={}".format(bc[:lb]))
    #print("ac={}".format(ac[:la]))
    """
    前処理終わり。これより実際の比較を行う。
    """
    ans = la + lb + lc
    for i in range(la + 1):
        for j in range(max(lb + 1, la - i + 1)): # A上でBとCがdisjointに乗っかっている場合、j <= lbだと不十分(ex: A = "qaawbbe", B = "aa", C = "bb")
            if ab[i] and bc[j] and ac[i + j]:
                preans = max(la, i + lb, i + j + lc) # ここ(i + lb)入れないと、Bが一番長い場合が抜け落ちる
                ans = min(ans, preans)
    #print("{}->{}->{}: ans={}".format(a, b, c, ans))
    return ans


def main():
    a = input()
    b = input()
    c = input()
    la = len(a)
    lb = len(b)
    lc = len(c)
    ans = func(a, b, c, la, lb, lc)
    ans = min(ans, func(a, c, b, la, lc, lb))
    ans = min(ans, func(b, a, c, lb, la, lc))
    ans = min(ans, func(b, c, a, lb, lc, la))
    ans = min(ans, func(c, a, b, lc, la, lb))
    ans = min(ans, func(c, b, a, lc, lb, la))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import chain, permutations, dropwhile
from heapq import merge
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wrapper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wrapper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
    if comp_wild(a[i:], b):
      yield i 

@listify
def connectors(a,b):
  for i in range(max(len(a)-len(b)+1, 1), len(a)+1):
    if comp_wild(a[i:], b):
      yield i

class c_int(int):
  def __new__(cls, *args, **kwargs):
    cond = kwargs.pop("cond", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cond = cond
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(a, b, c):
  keys = sorted((a,b,c), key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = { (i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  con = { (i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if (
        j+len_keys[2] <= i or i+len_keys[2] <= j or
        j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]
      ):
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      ( c_int(
          i+len_keys[z], 
          cond=lambda:(
            (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
            (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
            any(
              (i-j in con[y,z] if i > j else j-i in inc[z,y])
               for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y])
            )
          )
        ) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)
      ),
      ( c_int(
          min( i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p )
        ) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]
      ),
    )
  
  for c in merge(*( candicates(*xyz) for xyz in permutations(range(3), 3) )):
    if c.cond():
      return c
  
  return sum(len_keys)

print(solve(*(input() for i in range(3))))

Submission status: Accepted

Solution code:
import itertools

S = [input() for _ in range(3)]
MX = 2000
ans = MX*3
s = ['','','']
for s[0],s[1],s[2] in list(itertools.permutations(S,3)):
  d = [[[False for _ in range(MX)] for _ in range(3)] for _ in range(3)]
  for i in range(3):
    for j in range(3):
      if i >= j:
        continue
      for k in range(len(s[i])):
        f = True
        for ni in range(k,len(s[i])):
          nj = ni-k
          if nj >= len(s[j]):
            break
          if s[i][ni] == '?' or s[j][nj] == '?':
            continue
          if s[i][ni] != s[j][nj]:
            f = False
        d[i][j][k] = f
  
  def check(i,j,k):
    if k >= len(s[i]):
      return True
    return d[i][j][k]
  
  for x in range(MX):
    for y in range(MX):
      if not check(0,1,x):
        continue
      if not check(1,2,y):
        continue
      if not check(0,2,x+y):
        continue
      tmpans = 0
      tmpans = max(len(s[0]),tmpans)
      tmpans = max(x+len(s[1]),tmpans)
      tmpans = max(x+y+len(s[2]),tmpans)
      ans = min(tmpans,ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import chain, permutations, dropwhile
from heapq import merge
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wraper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wraper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
   if comp_wild(a[i:], b):
     yield i 

@listify
def connectors(a,b):
  for i in range(max(len(a)-len(b)+1, 1), len(a)+1):
    if comp_wild(a[i:], b):
      yield i

class c_int(int):
  def __new__(cls, *args, **kwargs):
    cond = kwargs.pop("cond", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cond = cond
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(a, b, c):
  keys = sorted((a,b,c), key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = { (i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  con = { (i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if (
        j+len_keys[2] <= i or i+len_keys[2] <= j or
        j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]
      ):
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      ( c_int(
          i+len_keys[z], 
          cond=lambda:(
            (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
            (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
            any(
              (i-j in con[y,z] if i>j else j-i in inc[z,y])
               for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y])
            )
          )
        ) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)
      ),
      ( c_int(
          min( i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p )
        ) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]
      ),
    )
  
  for c in merge(*( candicates(*xyz) for xyz in permutations(range(3), 3) )):
    if c.cond():
      return c
  
  return sum(len_keys)

print(solve(*(input() for _ in range(3))))

Submission status: Accepted

Solution code:
from itertools import chain, permutations, dropwhile
from heapq import merge
from functools import wraps

def listify(fn):
  @wraps(fn)
  def wraper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wraper

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
    if comp_wild(a[i:], b):
      yield i

@listify
def connectors(a,b):
  la = len(a)
  for i in range(max(la-len(b)+1, 1), la):
    if comp_wild(a[i-la:], b):
      yield i
  yield la

class c_int(int):
  def __new__(cls, *args, **kwargs):
    cond = kwargs.pop("cond", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cond = cond
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(a, b, c):
  keys = sorted((a,b,c), key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = { (i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  con = { (i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2) }
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if (
        j+len_keys[2] <= i or i+len_keys[2] <= j or
        j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]
      ):
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      ( c_int(
          i+len_keys[z], 
          cond=lambda:(
            (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
            (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
            any(
              (i-j in con[y,z] if i>j else j-i in inc[z,y])
               for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y])
            )
          )
        ) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)
      ),
      ( c_int(
          min( i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p )
        ) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]
      ),
    )
  
  for c in merge(*( candicates(*xyz) for xyz in permutations(range(3), 3) )):
    if c.cond():
      return c
  
  return sum(len_keys)

print(solve(*(input() for _ in range(3))))

Submission status: Accepted

Solution code:
from itertools import chain, permutations, dropwhile
from heapq import merge
from functools import wraps

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def listify(fn):
  @wraps(fn)
  def wraper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wraper

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
    if comp_wild(a[i:],b):
      yield i

@listify
def connectors(a,b):
  la = len(a)
  for i in range(max(la-len(b)+1, 1), la):
    if comp_wild(b, a[i-la:]):
      yield i
  yield la

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(a,b,c):
  keys = sorted((a,b,c), key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = {(i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  con = {(i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]:
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      
      (K(i+len_keys[z], cb=lambda:(
       (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
       (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
       any((i-j in con[y,z] if i>j else j-i in inc[z,y]) for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y]))
      )) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)),
      
      (K(min(i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p)) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]),
    )
  
  can = merge(*(candicates(*xyz) for xyz in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

print(solve(*(input() for _ in range(3))))

Submission status: Accepted

Solution code:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]:
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Accepted

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

OFFSETS = 9000


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = [True] * (OFFSETS * 2 + 10)
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j + OFFSETS] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx + OFFSETS] and check_ac[
                c_idx + OFFSETS] and check_bc[c_idx - b_idx + OFFSETS]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=[len(S[t])for t in X];q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import*;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Accepted

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