VK Cup 2015 - Finals A. Matching Names

問題文

http://codeforces.com/contest/566/problem/A

問題概要

n 個の名前と、n 個のペンネームが与えられる。これらを1対1対応させることを考える。
名前 a とペンネーム b をペアにした時の満足度を lcp(a, b) と定義する。
lcp(a, b) の総和が最大となるような、1対1対応を出力せよ。

1 <= n <= 10^5
文字列の長さの総和は 8 * 10^5

解法

lcp なので脳死で SA から攻めたくなりそうだが、lcp を Trie の上で考える視点も必要。
Trie における2文字列間の lcp は、LCA になる。
また、lcp(a, b) = (|a| + |b| - (|a| + |b| - 2 * lcp(a, b)) / 2 であることを考えると、lcp(a, b) の総和の最大化は（|a|, |b| が定数なので）以下のように言い換えられる。

木の上に n 頂点ずつ位置が与えられるので、それらをいい感じ組分けして最短距離の和の最小化をせよ

これは Trie を構築した後に dfs で下の方から貪欲的にペアを作っていけば達成できる。形式的に証明しなくても直感的にわかると思う。

これで計算量は O(total_length) となる。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct alphabet_t { // default: 'a' - 'z'
    static constexpr int size = 26;
    static constexpr int char_to_index(char c) {
        assert('a' <= c && c <= 'z');
        return c - 'a';
    }
    static constexpr char index_to_char(int idx) {
        assert(0 <= idx && idx < size);
        return 'a' + idx;
    }
};

template <typename Alpha>
class trie {
    static constexpr int alpha_sz = Alpha::size;

public:
    void insert(std::string const& s, int tag, int idx) {
        auto cur_node = this;
        for(int p = 0; p < static_cast<int>(s.size()); ++p) {
            const auto c = Alpha::char_to_index(s[p]);
            if(!cur_node->next[c]) cur_node->next[c] = std::make_unique<trie<Alpha>>();
            cur_node = cur_node->next[c].get();
        }
        cur_node->idxs[tag].push_back(idx);
    }

    // 本質
    pair<int, array<vector<int>, 2>> solve(std::vector<pii>& ans) {
        auto res = make_pair(0, idxs);
        for(int i = 0; i < alpha_sz; ++i) {
            if(!next[i]) continue;
            auto ch = next[i]->solve(ans);
            res.second[0].insert(end(res.second[0]), begin(ch.second[0]), end(ch.second[0]));
            res.second[1].insert(end(res.second[1]), begin(ch.second[1]), end(ch.second[1]));
            res.first += ch.first;
        }
        while(!res.second[0].empty() && !res.second[1].empty()) {
            ans.emplace_back(res.second[0].back(), res.second[1].back());
            res.second[0].pop_back();
            res.second[1].pop_back();
        }
        assert(res.second[0].empty() || res.second[1].empty());
        res.first += res.second[0].size() + res.second[1].size();
        return res;
    }

private:
    std::array<std::unique_ptr<trie<Alpha>>, alpha_sz> next;
    array<vector<int>, 2> idxs;
};


int main() {
    int n; cin >> n;
    trie<alphabet_t> t;
    int total_len = 0;
    for(int i = 0; i < 2 * n; ++i) {
        string s; cin >> s;
        t.insert(s, i >= n, (i >= n ? i - n + 1 : i + 1));
        total_len += s.size();
    }
    vector<pii> ans;
    cout << (total_len - t.solve(ans).first) / 2 << endl;
    for(auto& p : ans) {
        cout << p.first << " " << p.second << endl;
    }
}