Problem p02745 (python)

Fixed submission:

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

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

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

ml = max(la, lb, lc)

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

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

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


def main():

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


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

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

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

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

    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

def main():

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

    def LCS(S, T):

        if len(S) == 0 or len(T) == 0:
            return 0
        

        dp = [[0 for _ in range(len(S) + 1)] for _ in range(len(T) + 1)]
        for i in range(len(S)):
            for j in range(len(T)):
                if S[i] == "?" or T[j] == "?" or S[i] == T[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

        return dp[len(S)][len(T)]

    ans = 0

    ab = LCS(a,b)

    ac = LCS(a,c)

    bc = LCS(b,c)


    if ab == ac == bc == 0:
        print(len(a) + len(b) + len(c))
        exit()

    if ac <= ab and ac <= bc:
        ans = (len(a) + len(b) - ab) + (len(c) - bc) 

    elif ab <= ac and ab <= bc:
        ans = (len(a) + len(c) - ac) + (len(c) - bc) 

    elif bc <= ab and bc <= ac:
        ans = (len(a) + len(b) - ab) + (len(c) - ac)

    print(ans) 


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

def main():

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

    def LCS(S, T):
        dp = [[0 for _ in range(len(S) + 1)] for _ in range(len(T) + 1)]
        for i in range(len(S)):
            for j in range(len(T)):
                if S[i] == "?" or T[j] == "?" or S[i] == T[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

        return dp[len(S)][len(T)]

    ans = 0

    ab = LCS(a,b)

    ac = LCS(a,c)

    bc = LCS(b,c)


    if ab == ac == bc == 0:
        print(len(a) + len(b) + len(c))
        exit()

    if ac <= ab and ac <= bc:
        ans = (len(a) + len(b) - ab) + (len(c) - bc) 

    elif ab <= ac and ab <= bc:
        ans = (len(a) + len(c) - ac) + (len(c) - bc) 

    elif bc <= ab and bc <= ac:
        ans = (len(a) + len(b) - ab) + (len(c) - ac)

    print(ans) 


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):



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

def LCS(S, T):
    dp = [[0 for _ in range(len(S) + 1)] for _ in range(len(T) + 1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == "?" or T[j] == "?" or S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    return dp[len(S)][len(T)]

ans = 0

ab = LCS(a,b)

ac = LCS(a,c)

bc = LCS(b,c)


if ab == ac == bc == 0:
    print(len(a) + len(b) + len(c))
    exit()

if ac <= ab and ac <= bc:
    ans = (len(a) + len(b) - ab) + (len(c) - bc) 

elif ab <= ac and ab <= bc:
    ans = (len(a) + len(c) - ac) + (len(c) - bc) 

elif bc <= ab and bc <= ac:
    ans = (len(a) + len(b) - ab) + (len(c) - ac)

print(ans)