Google Code Jam 2019 Round 1A : Alien Rhyme

問題. Alien Rhyme

英大文字からなる $N$ 個の単語が与えれる．各単語に任意に1つアクセントを付ける．アクセントから末尾までの部分文字列をその単語のアクセント接尾辞と呼ぶことにする．2つの異なる単語が同じアクセント接尾辞を持つとき，それらの単語は韻を踏んでいるという． $N$ 個の単語からいくつかのペアを作る．ただし，各ペアは韻を踏んでおり，どの単語も複数のペアに含まれていないとする．また，異なるペア間のアクセント接尾辞はどれも異なるものとする．このようなペアを最大でいくつ選ぶことができるかを答えよ．

制約： $1 \le N \le 1,000$ ，　 $1 \le w_i \le 50$ （ $w_i$ は $i$ 番目の単語）

解法

接尾辞は各単語の長さが異なるときに扱いにくいので，各単語を逆順にして接頭辞で考える．Trie木を考えると，葉以外の頂点 $v$ に対して， $v$ でアクセントを取るということは，根から $v$ までの道に対応する文字列がアクセント接頭辞として選ばれたということを意味している．どの異なる2つのペアも同じアクセント接頭辞を取らないということは， $v$ でアクセントを付けてペアとして選ぶことができるのは高々1組ということが分かる．以上の考察から，Tire木の葉の方向からまだ選ばれていない単語を貪欲的にペアにすることによって答えが求まる．
本番ではTrie木を陽に持たずに実装した．ペアの選び方は $\binom{N}{2}$ 通りあり，各組に対してその最長の接頭辞を求める．そして，解の候補の中で接頭辞が長いペア（どの単語も解に選ばれていないもの）から貪欲的に解の候補として考える．このとき，そのペアの接頭辞が既に選ばれている場合は，接頭辞を1文字づつ短くしてチェックする．この操作は，2つの単語に対応する葉の最長共通祖先から根へアクセントを変更することに対応する．
実際にTrie木を実装した方がより高速に解を求めることができるはず．

計算時間： $O(W^2 N^2 \log N)$ 　（ $W = max_{1 \le i \le N} |w_i|$ ）

ソースコードを表示（実装1）

#include <bits/stdc++.h>

using namespace std;

struct Data {
    string prefix;
    int idx1, idx2;
    Data() {}
    Data(string s, int i1, int i2) : prefix(move(s)), idx1(i1), idx2(i2) {}
};
bool operator<(const Data &d1, const Data &d2) {
    return (d1.prefix.size() > d2.prefix.size()) ||
        (d1.prefix.size() == d2.prefix.size() && d1.prefix < d2.prefix);
}

string prefix(const string &s, const string &t) {
    const int len = min(s.size(), t.size());
    int idx = 0;
    while (idx < len && s[idx] == t[idx]) ++idx;
    return s.substr(0, idx);
}

int Solve() {
    int n;
    cin >> n;

    vector<string> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        reverse(w[i].begin(), w[i].end());
    }

    vector<Data> data; data.reserve(n * (n - 1) / 2);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            data.emplace_back(Data(prefix(w[i], w[j]), i, j));
        }
    }
    sort(data.begin(), data.end());

    vector<bool> used(n, false);
    set<string> memo;
    for (auto &it : data) {
        if (used[it.idx1] || used[it.idx2]) continue;
        while (0 < it.prefix.size() && memo.count(it.prefix) != 0)
            it.prefix.pop_back();
        if (it.prefix.size() != 0) {
            used[it.idx1] = used[it.idx2] = true;
            memo.insert(it.prefix);
        }
    }

    return count(used.begin(), used.end(), true);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int T;
    cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        cout << "Case #" << i_case << ": " << Solve() << endl;
    }

    return 0;
}

　
　
Trie木を意識した実装で時間計算量は $O(W N \log N)$ である．こちらの方が高速で実装もシンプル．

ソースコードを表示（実装2）

#include <bits/stdc++.h>

using namespace std;

template<typename Iterator>
int Rec(size_t idx_accent, Iterator begin, Iterator end) {
    if (distance(begin, end) <= 1) return 0;

    Iterator iter = begin;
    while (iter != end && iter->size() <= idx_accent) ++iter;
    int num_match = (distance(begin, iter) <= 1 ? 0 : 2);

    for (begin = iter; begin != end; ) {
        while (iter != end && (*begin)[idx_accent] == (*iter)[idx_accent]) ++iter;

        const int num_words = distance(begin, iter);
        const int num_res = Rec(idx_accent + 1, begin, iter);
        if (2 <= num_words - num_res) num_match += 2 + num_res;
        else num_match += num_res;
        begin = iter;
    }

    return num_match;
}

int Solve() {
    int n;
    cin >> n;

    vector<string> w(n);
    for (auto &s : w) {
        cin >> s;
        reverse(s.begin(), s.end());
    }
    sort(w.begin(), w.end());

    return Rec(0, w.begin(), w.end());
}


int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int T;
    cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        cout << "Case #" << i_case << ": " << Solve() << endl;
    }

    return 0;
}

出力のフォーマットをミスってWAを貰ったのが残念．