概要

\(N\) 人の社員に対し、各ユーザー名の空でない接頭辞を略称として割り当て、略称集合が接頭辞フリーとなるようにしつつ、略称の長さの合計を最小化する問題です。トライ木上での貪欲法により解くことができます。

考察

不可能な場合の判定

もしユーザー名 \(S_i\) が別のユーザー名 \(S_j\) の接頭辞であった場合、\(T_i\) として選べるのは \(S_i\) の接頭辞だけですが、それはすべて \(S_j\) の接頭辞でもあります。よって \(T_i\) は必ず \(T_j\) の接頭辞となり、接頭辞フリー条件を満たせません。この場合は \(-1\) を出力します。

トライ木上での問題の言い換え

すべてのユーザー名をトライ木に挿入すると、上記の不可能ケースを除けば、すべてのユーザー名はトライ木の葉に対応します。

各社員 \(i\) に略称 \(T_i\) を割り当てることは、トライ木上でその社員の文字列のパス（根から葉まで）の中から1つのノードを選ぶことに対応します。接頭辞フリー条件は「選ばれたノード集合が反鎖（antichain）である、すなわちどの2ノードも祖先・子孫の関係にない」ことと同値です。

貪欲法の着想

略称は短いほど良いので、できるだけ浅いノード（短い接頭辞）を割り当てたいです。

あるノードの部分木に含まれる葉（ユーザー名）が1つだけであれば、そのノードをその唯一の社員の略称として割り当てられます。なぜなら、他のどの社員のパスもこのノードを通らないので、衝突が起きないからです。

逆に、部分木に2つ以上の葉がある場合、そのノードを誰かに割り当てると、同じ部分木内の他の社員の略称はそのノードの子孫になってしまい、接頭辞フリー条件に違反します。よって、こうしたノードでは割り当てを行わず、さらに深い子ノードへ進みます。

アルゴリズム

1. トライ木を構築: すべてのユーザー名を挿入する。
2. 不可能判定: 文字列が終端するノードに子がある場合（ある文字列が別の文字列の接頭辞）、\(-1\) を出力。
3. 部分木の葉数を計算: 各ノードについて、部分木に含まれる葉の数（leaf_count）を求める。
4. BFS で貪欲に割り当て: 根の子ノードからBFSで探索し、
   • leaf_count[node] == 1 のとき：そのノードの深さ（= 接頭辞の長さ）を答えに加算し、それ以上深く探索しない。
   • leaf_count[node] >= 2 のとき：子ノードをキューに追加して探索を続ける。
5. 全員に割り当てできたら合計を出力、そうでなければ \(-1\) を出力。

具体例

ユーザー名が abc, abd, xyz の場合のトライ：

root → a → b → c (葉: "abc")
              → d (葉: "abd")
     → x → y → z (葉: "xyz")

• ノード x（深さ1）: 部分木に葉1つ → "xyz" に長さ1の略称 "x" を割り当て
• ノード a（深さ1）: 部分木に葉2つ → 割り当てず、子へ進む
• ノード ab（深さ2）: 部分木に葉2つ → 割り当てず、子へ進む
• ノード abc（深さ3）: 部分木に葉1つ → "abc" に略称 "abc" を割り当て
• ノード abd（深さ3）: 部分木に葉1つ → "abd" に略称 "abd" を割り当て

合計: \(1 + 3 + 3 = 7\)

計算量

• 時間計算量: \(O(\sum |S_i|)\)（トライの構築、葉数計算、BFS探索がすべて文字列の総長に比例）
• 空間計算量: \(O(\sum |S_i|)\)（トライのノード数は文字列の総長以下）

実装のポイント

• \(N = 1\) の場合は必ず長さ1の略称を割り当てられるので、先に処理する。

• トライのノードIDは挿入順に振られるため、子ノードは必ず親より大きいIDを持つ。これを利用して、IDの降順に走査することで葉数を親に伝播できる（逆順ループで leaf_count[parent[i]] += leaf_count[i]）。

• 根ノード（深さ0）は空文字列に対応するため、割り当て対象にしない。\(N \geq 2\) なら根の leaf_count は必ず2以上なので、根が選ばれることはない。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    
    strings = []
    for i in range(N):
        s = tokens[idx]; idx += 1
        strings.append(s)
    
    if N == 1:
        print(1)
        return
    
    # Build a trie
    # Each node: children[0..25], count of strings that pass through or end here
    # We need to track: how many strings have this node as a prefix of their full string
    # and whether a string ends exactly at this node
    
    # Trie node: children dict, end_count (number of strings ending here), pass_count (number of strings passing through, i.e., having longer extensions)
    # Actually, let's think differently.
    
    # Build trie. For each node, we know:
    # - How many strings end at this node (end_here)
    # - How many strings pass through this node (i.e., have this node's path as a proper prefix) 
    
    # For the prefix-free assignment:
    # Each string S_i must pick some prefix T_i (a node in the trie on S_i's path)
    # No T_i is a prefix of T_j for i != j
    # This means all chosen nodes form an antichain in the trie (no ancestor-descendant relation)
    # Minimize sum of depths (depth = length of prefix)
    
    # This is equivalent to: in the trie built from all strings, for each string (leaf path),
    # pick exactly one node on its root-to-end path, such that no two picked nodes are
    # on the same root-to-leaf path (antichain), and minimize total depth.
    
    # Since each S_i is distinct, we build the trie and each string ends at a unique node.
    
    # Key insight: We need to assign each string to a node on its path (from root to its end node).
    # The chosen nodes must form a prefix-free set (antichain in trie).
    # A node can be chosen by at most one string (since if two strings share a prefix node and both pick it, they'd pick the same node which means T_i = T_j, violating prefix-free).
    
    # This is a matching/assignment problem on the trie.
    
    # Greedy approach: Process trie nodes level by level (BFS, shortest first).
    # At each node, if exactly one unassigned string passes through it, assign that string to this node.
    # But this doesn't quite work because a node might be on the path of multiple unassigned strings.
    
    # Better: Think of it as a flow/greedy on trie.
    # At each internal node with children, the strings split. If a node has only one string passing through it, that string can claim this node.
    # We process top-down greedily: at each node, if only one string uses it, assign at this depth.
    # If multiple strings share this node, they must go deeper.
    # If a string ends at a shared node (other strings continue deeper), it's impossible for that string to avoid conflict... unless it takes this exact node and others go deeper. But then this node is an ancestor of deeper nodes, violating prefix-free. So actually the string ending here CANNOT take this node if other strings go deeper and might take descendants. Wait - the other strings take nodes that are descendants, and this string takes this node -> this node is a prefix of descendants -> violates prefix-free.
    
    # So if a string ends at a node that is a proper prefix of another string, that string MUST take its full name, but that full name node is an ancestor of deeper nodes... The string ending here can only pick prefixes up to its length. If another string extends beyond, any prefix the short string picks is a prefix of the long string's path. The long string must pick a node on its path that is NOT a descendant of the short string's chosen node. But the short string's chosen node is on the shared path... Actually the long string's node could be on a different branch? No, the long string goes through all ancestors.
    
    # If S_i is a proper prefix of S_j, then every possible T_i (prefix of S_i) is also a prefix of S_j, hence a prefix of any T_j. So T_i is always a prefix of T_j -> impossible to satisfy prefix-free.
    
    # So first check: if any S_i is a prefix of S_j, output -1.
    
    # After that, all strings end at leaf nodes of the trie (no string is a prefix of another).
    
    # Now the problem: assign each leaf (string) to some ancestor node, antichain, minimize total depth.
    
    # Greedy: BFS top-down. At each node, count how many leaves are in its subtree.
    # If a node has exactly 1 leaf in subtree, assign that leaf to this node.
    # This is optimal because taking a shorter prefix is always better.
    
    # Implementation with trie:
    
    # Build trie
    # Node: list of children, is_end, subtree_leaf_count
    
    MAX_NODES = 500002
    children = [None] * MAX_NODES
    is_end = [False] * MAX_NODES
    depth = [0] * MAX_NODES
    parent = [0] * MAX_NODES
    node_count = 1  # root is 0
    
    # Check prefix condition and build trie
    for s in strings:
        cur = 0
        for ch in s:
            c = ord(ch) - ord('a')
            if children[cur] is None:
                children[cur] = {}
            if c not in children[cur]:
                children[cur][c] = node_count
                depth[node_count] = depth[cur] + 1
                parent[node_count] = cur
                node_count += 1
            cur = children[cur][c]
        is_end[cur] = True
    
    # Check: if any string is a prefix of another
    # A string ends at node X. If X is not a leaf in the trie (has children), then some other string extends beyond -> S_i is prefix of S_j.
    for i in range(node_count):
        if is_end[i] and children[i] is not None and len(children[i]) > 0:
            print(-1)
            return
    
    # Now all strings end at trie leaves.
    # Compute subtree leaf count for each node.
    leaf_count = [0] * node_count
    for i in range(node_count):
        if is_end[i]:
            leaf_count[i] = 1
    
    # Process in reverse order (children before parents) - since node IDs are assigned in BFS/DFS order,
    # children always have higher IDs than parents.
    for i in range(node_count - 1, 0, -1):
        leaf_count[parent[i]] += leaf_count[i]
    
    # Greedy: for each node (BFS top-down), if leaf_count == 1, assign that leaf to this node.
    # The cost is depth[node] (which equals prefix length since root has depth 0... actually depth of root is 0, 
    # and a prefix of length k corresponds to a node at depth k).
    # Wait, depth[node] = number of characters from root to node = length of prefix. Root = 0 = empty string.
    # But we need non-empty prefix, so minimum depth is 1.
    
    # When leaf_count[node] == 1, assign at this node if depth >= 1.
    # The root (depth 0) corresponds to empty prefix which is not allowed.
    # If root has leaf_count 1 (N=1), we handle that separately (already done above).
    
    # For N >= 2, root has leaf_count >= 2, so root won't be assigned.
    # A node at depth 1 with leaf_count 1 -> assign, cost = 1.
    
    # Once assigned, we "remove" that leaf from ancestor counts. But actually, 
    # the greedy is: traverse top-down, and whenever leaf_count == 1, this subtree's single leaf 
    # gets assigned here. We add depth[node] to answer and don't recurse further.
    
    # BFS
    ans = 0
    assigned = 0
    queue = deque()
    # Start from root's children (root itself is depth 0 = empty prefix, not valid)
    if children[0] is not None:
        for c, child in children[0].items():
            queue.append(child)
    
    while queue:
        node = queue.popleft()
        if leaf_count[node] == 1:
            # Assign the single leaf in this subtree to this node
            ans += depth[node]
            assigned += 1
        else:
            # leaf_count[node] >= 2, go deeper
            if children[node] is not None:
                for c, child in children[node].items():
                    queue.append(child)
    
    if assigned == N:
        print(ans)
    else:
        print(-1)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。