Kick Start Round A 2020

　Dが解けず。
　コンテスト中もTrie木を使うのかな、とは思ったようですが……。

コンテストへのリンク
コンテスト後のツイート

Bundling

　（英語だけど）この動画解説を参考にした。……けど、Trieが頭に入っていればそれほど難しくないね。簡単な木DPで解けます。

　Trieについては、kami634さんの記事が詳しいし分かりやすい。上の動画でTrieの概要は理解できたのだけど、実装をどうすれば良いか分からなくなったときこの記事が参考になった。感謝。

　実装方針が分かってしてしまえば意外と書くのは簡単だったけれど、自分で最初実装を考えたときは、辞書を使って云々しなくてはいけない気がしてしまい困った。ノードが追加されるたびに、新しいidを割り当てるようにすれば良いですね。

　ACした提出を一応載せておきます。（見ての通り、Trieをclassにしたりはしてません）

import sys
input = sys.stdin.readline
 
T = int(input())
for testcases in range(T):
    N,K=map(int,input().split())
 
    # Trie木
 
    Next_node_id=[[-1]*26] # "A"～"Z"それぞれについて、対応する次のノードのid
    Parent_id=[-1] # 親ノード
    Depth=[0] # Trieのノードの深さ
    Count=[0] # Trieのノードの重複度
 
    Nodes_id=1 # 以下、標準入力で与えられたN個の文字列を追加する実装
    for i in range(N):
        S=input().strip()
        L=len(S)
 
        NOW=0
        for s in S:
            NEXT=ord(s)-65
            
            if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
                Next_node_id[NOW][NEXT]=Nodes_id
 
                Next_node_id.append([-1]*26)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)
 
                NOW=Nodes_id         
                Nodes_id+=1
 
            else: # 追加しない場合
                NOW=Next_node_id[NOW][NEXT]
 
        Count[NOW]+=1 # 終端に印を付ける
 
    TOP_SORT=sorted([(dep,id) for id,dep in enumerate(Depth)],reverse=True)
 
    Rest=[0]*len(TOP_SORT)
    ANS=0
 
    for dep,n in TOP_SORT:
        c=Count[n]+Rest[n]
        ANS+=Depth[n]*(c//K)
        Rest[Parent_id[n]]+=c%K
 
    print("Case #"+str(testcases+1)+": "+str(ANS))