gcj2019_1a_c.py

import copy
T = int(input())

def calc_min_len(ws):
    min_len = 999999
    for w in ws:
        l = len(w)
        if l < min_len:
            min_len = l
    return min_len


def check_words_clear(words):
    for w in words:
        if w != "":
            return True
    return False    


def find_rhyme(words, used_suffix, num, min_len):
    #print("find_rhyme", num, min_len, words)
    if num > min_len:
        return 0
    if not(check_words_clear(words)):
        return 0

    lengths = [0]
    for i in range(len(words)):
        if words[i] == "" or words[i][-num:] in used_suffix:
            continue

        for j in range(i+1, len(words)):
            if words[j] == "":
                continue
            if words[i][-num:] == words[j][-num:]:
                #print("use", words[i], words[j])
                words2 = copy.deepcopy(words)
                used_suffix2 = copy.deepcopy(used_suffix)
                used_suffix2.append(words[i][-num:])
                words2[i] = ""
                words2[j] = ""
                len2 = 2 + find_rhyme(words2, used_suffix2, num, min_len)
                len2 += find_rhyme(words2, used_suffix2, num+1, min_len)
                lengths.append(len2)
    return max(lengths)


for cnt in range(T):
    N = int(input())
    words = [input() for _ in range(N)]

    print("Case #"+str(cnt+1)+":", str(find_rhyme(words, [], 1, calc_min_len(words))))

Sampleは通りましたがWAです