Google Kickstart 2020 RoundA - Bundling問題の解説

Kickstart2020 RoundAのBundlingの問題です。

問題

N個の文字列が与えられて、これをK個毎のグループに分ける場合（グループ数はN/K）、各グループのスコアをグループに属する全文字列のcommon longest prefix長とした時、最大となるスコアを求めるというものです。
スコアの計算は、例えば{RAINBOW, RANK, RANDOM, RANK}というグループであれば、RAがlongest prefix長なので2となります。

アルゴリズム

ここの動画を参考にしました。
与えられた文字列から、26文字分のchildノードを持つTrieを作ります。またこの時、Trieのノードはカウントを持ち、このノードが末尾の文字となる文字列の数を保持します。すべての文字列を追加した後は、TrieをPost orderで探索して、各ノードでK以上のカウントになった場合に、Trie木のdepthの値をスコアに加算していくと解を得ることができます（グループが出来て、グループに属するprefix長がdepthに相当）。

実装

Trie木のノードを表すstructであるTrieNodeは、26要素のchild nodes、文字列数を保持するcountを持ちます。insertはTrieへの文字列の挿入処理、calc_scoreはTrieをPost orderで探索し、スコアを求める処理になっています。

#include <bits/stdc++.h>

using namespace std;
typedef struct _TrieNode
{
    _TrieNode *child[26];
    int count = 0;
} TrieNode;

void insert(TrieNode *root, string &s)
{
    TrieNode *curr = root;
    for (int i = 0; i < s.size(); ++i)
    {
        int idx = s[i] - 'A';
        if (!curr->child[idx])
        {
            curr->child[idx] = new TrieNode();
        }
        curr = curr->child[idx];
    }
    curr->count++;
}

int calc_score(TrieNode *root, int depth, int K)
{
    int curr_score = 0;
    for (int i = 0; i < 26; ++i)
    {
        if (root->child[i])
        {
            int score = calc_score(root->child[i], depth + 1, K);
            curr_score += score;
            root->count += root->child[i]->count;
        }
    }
    while (root->count >= K)
    {
        root->count -= K;
        curr_score += depth;
    }
    return curr_score;
}

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        TrieNode *root = new TrieNode();
        int N, K;
        cin >>
            N >> K;
        string strings[N];
        for (int i = 0; i < N; ++i)
        {
            cin >> strings[i];
            insert(root, strings[i]);
        }
        int score = calc_score(root, 0, K);
        cout
            << "Case #" << t << ": " << score << endl;
        delete root;
    }
    return 0;
}

https://github.com/satojkovic/algorithms/blob/master/kickstart/2020/RoundA/bundling.py