Editorial - AtCoder Beginner Contest 416

Contest Duration: 2025-07-26 21:00:00+0900 - 2025-07-26 22:40:00+0900 (local time) (100 minutes) Back to Home

G - Concat (1st) Editorial by MMNMM

より高速な解法

全体で \(O(\sum\left\vert S _ i\right\vert+\vert\Sigma\vert)\) 時間となる解法について解説します（厳密には、答えの長さをこの時間で求める解法です）（ネタバレ：答えとなる文字列を構築するパートを除いてもこの時間計算量を実現する実装例はこの解説中にはありません。log がついた実装例はあります）。

長さ \(N\) の非負整数列 \(A\) に対して、適当な \(O(N)\) 時間の前計算によって、整数 \(l,r\ (1\le l\le r\le N)\) に対する \(A _ l,A _ {l+1},\ldots,A _ r\) の最小値を求めることをクエリあたり \(O(1)\) 時間で行うことができます。

これと Suffix Array および LCP Array を利用することで、長さ \(N\) の文字列 \(S\) に対して、適当な \(O(N+\vert\Sigma\vert)\) 時間の前計算によって、整数 \(l _ 1,r _ 1,l _ 2,r _ 2\ (1\le l _ 1\le r _ 1\le N,1\le l _ 2\le r _ 2\le N)\) に対して \(S\) の部分文字列 \(S\lbrack l _ 1\colon r _ 1\rbrack\) と \(S\lbrack l _ 2\colon r _ 2\rbrack\) を辞書順で比較することがクエリあたり \(O(1)\) 時間でできます。

上記を用いて、文字列の列 \((S _ 1,S _ 2,\ldots,S _ N)\) に対して、適当な \(O(\sum\left\vert S _ i\right\vert+\vert\Sigma\vert)\) 時間の前計算によって、整数 \(i,j\ (1\le i\lt j\le N)\) に対して \(S _ i ^ {\infty}\) と \(S _ j ^ {\infty}\) を辞書順で比較することがクエリあたり \(O(1)\) 時間でできます（すべてを連結した文字列について Suffix Array, LCP Array を構築し、\(S _ i+S _ j\) と \(S _ j+S _ i\) の比較へ言い換えたのち、たかだか \(3\) 組の連続する部分文字列どうしの辞書順比較とすることができます）。

公式解説の内容を前提とします。特に、全順序 \(\preceq\) に対する最小元 \(S _ i\) について、答えが

\(S _ i ^ \infty\) の prefix のうち、\(S _ 1,S _ 2,\ldots,S _ N\) を \(K\) 個連結して得られる最短のもの

であることを利用します。

いずれかの \(K\) における辞書順最小の文字列を与える列 \((A _ 1,A _ 2,\ldots,A _ K)\) に含まれる \(a\) について、\(S _ a\) は \(S _ i\) の prefix である必要があります。

証明

\(a\) が \(A\) の先頭にあるとして構いません。 \(A\) の先頭から \(a\) を取り除いた列 \(A ^ \prime\) に対する \(f(A ^ \prime)\) は \(K-1\) に対する答えなので、特に \(S _ i ^ \infty\) の prefix です。すると、\(S _ i+f(A ^ \prime)\) は \(S _ i ^ \infty\) の prefix であって \(S _ 1,S _ 2,\ldots,S _ N\) を \(K\) 個連結して得られるものになります。よって、\(a\) が \(K\) に対する答えを与えることから、\(S _ i+f(A ^ \prime)\) の長さは \(f(A)\) 以上でなければならず、\(\vert S _ a\vert\le\vert S _ i\vert\) が成り立ちます。 \(S _ a\) は \(S _ i ^ \infty\) の prefix なので、長さの条件とあわせて \(S _ i\) の prefix であることが示されました。

よって、\((S _ 1,S _ 2,\ldots,S _ N)\) （および \(N\)）を答えが変わらないように

\(S _ i\) が \(S _ {i+1}\) の prefix である \((1\le i\lt N)\)
\(S _ N\preceq S _ i\ (1\le i\le N)\)

が成り立つように取り直すことができます。

これは上述のアルゴリズムとあわせて \(O(\sum\vert S _ i\vert+\vert\Sigma\vert)\) 時間で実行することができます。

ここで、アルファベット \(\Sigma\) を \(\lbrace1,2,\ldots,\sigma\rbrace\) とし、十分小さい正実数 \(\varepsilon\) をとって、文字列 \(S\) に対して \(\displaystyle v(S)\coloneqq\sum _ {i=0} ^ {\vert S\vert}S _ i\varepsilon ^ i\) と定義します（この後 \(v\) を無限長の文字列に対しても断りなく使いますが、無限和が収束するような小さい \(\varepsilon\) をとっています）。このとき、辞書順で \(S\lt T\) であることは \(v(S)\lt v(T)\) であることと同値です。

ここで、文字列の連結に対して \(v(S+T)=v(S)+\varepsilon ^ {\vert S\vert}v(T)\) が成り立ちます。よって、\(K-1\) に対する答え \(X\) から \(K\) に対する答え \(S _ i+X\) を求めることは、一次関数群 \(P _ {S _ i}(x)=v(S _ i)+\varepsilon ^ {\vert S _ i\vert}x\) の \(x=v(X)\) における最小値（を与える一次関数）を求めることに対応します。これらの一次関数群に対して前処理を行うことで、この最小値（を与える一次関数）を高速に求めることができます（Convex Hull Trick と呼ばれます）。

前処理に際して、\(S _ i\) とその prefix \(S _ j\) に対して \(P _ {S _ i}\) と \(P _ {S _ j}\) の交点を求める必要があります。これは、\(S _ i\) の \(\vert S _ j\vert\) 文字目以降（\(S _ i\) の \(S _ j\) に含まれていない部分）を \(s\) として \(x=v(s ^ \infty)\) です。また、クエリの処理において適当な文字列 \(T\) と \(s ^ \infty\) を辞書順で比較する必要があります。これは \(T\) と \(sT\) を比較することに帰着されます（ARC175 F 解説の補題 2）。

空文字列（\(K=0\) のときの答え）からはじめて \(K\) を増やしていくことを考えます。一度 \(S _ N\) が選ばれたらその後は常に \(S _ N\) が選ばれ続けるため、\(S _ N\) が一度選ばれるまで増やせば十分です。 \(S _ N\) が選ばれるための条件について考えます。

\(S _ N\) とその直前の直線との交点は（存在すれば）、ある \(S _ N\) の suffix \(s\) が存在して \(s ^ \infty\) とかける（無限長の）文字列に対応する点です。これより答え \(X\) が大きくなったとき、\(S _ N\) が選ばれるようになります。まず、\(s ^ \infty\) と \(S _ N ^ \infty\) は異なります。そうでない場合、\(S _ N\) および \(s\) はある文字列 \(p\) が存在して \(p\) を何度か繰り返した文字列です。ここで、\(S _ i\) を \(S _ N\) の直前の直線に対応する文字列としたとき、\(S _ i\) も \(p\) を繰り返した文字列となります。これは \(S _ i\preceq S _ N\) を意味しており、これは \(S _ N\) の最小性に反します。 \(s ^ \infty\) と \(S _ N ^ \infty\) の LCP の長さについて考えます。これは、上記の解説の補題 1 より、\(s+S _ N\) と \(S _ N+s\) の LCP の長さと一致します。これはたかだか \(2\vert S _ N\vert\) であるので、\(K\) を増やすのもここまでで十分であることがわかります。

いま、\(S _ i\) が \(S _ {i+1}\) の prefix であるよう \(S\) を取り直したため、\(P _ {S _ i}(x)\) は傾きの降順に並んでいます。また、\(K\) が増えるたびに \(v(X)\) も増加するため、答えが（前処理を除いて） \(O(\vert S _ N\vert+N)\) 時間で求められました。

実装例は以下のようになります。

以下の実装例では文字列の比較を \(O(\vert S\vert+\vert T\vert)\) 時間で行っています。 Static RMQ の実装をサボって比較が \(O(\log\sum\vert S _ i\vert)\) 時間になっている実装例も載せておきますが、長いので折りたたみとします。

以下の実装例では、同じ長さの文字列については辞書順最小のものしか保管する必要がないことを利用して定数倍を削減しています（？）

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;

    // それぞれの長さで辞書順最小のもののみ見れば十分
    constexpr unsigned max_size{10};
    vector<string> A(max_size + 1);
    for (unsigned i{}; i < N; ++i) {
        string S;
        cin >> S;
        const auto L{size(S)};
        if (empty(A[L]))
            A[L] = move(S);
        else
            A[L] = min(A[L], move(S));
    }
    // なかった長さは消す
    erase_if(A, [](const auto& s) { return empty(s); });

    // S^∞ と T^∞ を比較する（同じなら短いほうが小さいとする）
    const auto compare_infinite_repeat{[](const auto& lhs, const auto& rhs) {
        return lhs + rhs == rhs + lhs ? lhs < rhs : lhs + rhs < rhs + lhs;
    }};

    // 答えは minimum_S の繰り返しの prefix になる
    const auto minimum_S{ranges::min(A, compare_infinite_repeat)};
    // minimum_S の prefix 以外は使われない
    erase_if(A, [&minimum_S](const auto& s) { return !minimum_S.starts_with(s); });

    // CHT の準備
    vector<pair<string, string>> segments;
    for (const auto& s : A) {
        while (!empty(segments) && compare_infinite_repeat(s.substr(size(segments.back().first)), segments.back().second))
            segments.pop_back();
        if (empty(segments))
            segments.emplace_back(s, ""s);
        else
            segments.emplace_back(s, s.substr(size(segments.back().first)));
    }

    // S^∞ と T を比較する
    const auto compare_partially_infinite_repeat{[](const auto& lhs, const auto& rhs) {
        return lhs + rhs < rhs;
    }};

    // CHT を使って適切な prefix を求める
    string ans{};
    for (unsigned i{}, j{1}; i < K; ++i) { // たかだか 2 * size(minimum_S) 回しかループは回らない
        while (j < size(segments) && compare_partially_infinite_repeat(segments[j].second, ans))
            ++j;
        if (j == size(segments)) {
            string tmp{};
            for (unsigned k{i}; k < K; ++k)
                tmp += segments.back().first;
            ans = tmp + ans;
            break;
        }
        ans = segments[j - 1].first + ans;
    }
    cout << ans << endl;
    return 0;
}

logがついているほう

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <ranges>
#include <atcoder/segtree>
#include <atcoder/string>

int main() {
    using namespace std;
    class string_segment_comperator {
        const string s;
        const vector<unsigned> suffix_array, suffix_array_inv;
        const atcoder::segtree<unsigned, [](const auto a, const auto b) { return min(a, b); }, []{return numeric_limits<unsigned>::max();}> lcp_segtree;
    public:
        string_segment_comperator(const string& s) : s{s}, suffix_array([](const vector<int> &seq){
            vector<unsigned> result(size(seq));
            for (unsigned i{}; i < size(seq); ++i)
                result[i] = seq[i];
            return result;
        }(atcoder::suffix_array(s))), suffix_array_inv([](const vector<unsigned> &seq){
            vector<unsigned> result(size(seq));
            for (unsigned i{}; i < size(seq); ++i)
                result[seq[i]] = i;
            return result;
        }(suffix_array)), lcp_segtree([](const vector<int> &seq){
            vector<unsigned> result(size(seq));
            for (unsigned i{}; i < size(seq); ++i)
                result[i] = seq[i];
            return result;
        }(atcoder::lcp_array(s, [](const vector<unsigned> &seq){
            vector<int> result(size(seq));
            for (unsigned i{}; i < size(seq); ++i)
                result[i] = seq[i];
            return result;
        }(suffix_array)))) {}
        strong_ordering check(unsigned i, unsigned j, unsigned n) const {
            if (i == j)
                return strong_ordering::equal;
            assert(i + n <= size(s));
            assert(j + n <= size(s));
            if (suffix_array_inv[i] > suffix_array_inv[j])
                return 0 <=> check(j, i, n);
            const auto l{lcp_segtree.prod(suffix_array_inv[i], suffix_array_inv[j])};
            return l >= n ? strong_ordering::equal : s[i + l] < s[j + l] ? strong_ordering::less : strong_ordering::greater;
        }
        const string& str() const {
            return s;
        }
    };
    const auto infinite_repeat_compare_from_comperator{[](const auto& comperator){
        return [&comperator](const auto& lhs, const auto& rhs) {
            const auto &[ll, lr]{lhs};
            const auto &[rl, rr]{rhs};
            const auto L{lr - ll}, R{rr - rl};
            if (L < R) {
                const auto first_segment{comperator.check(ll, rl, L)};
                if (first_segment != strong_ordering::equal)
                    return first_segment < 0;
                const auto second_segment{comperator.check(rl, rl + L, R - L)};
                if (second_segment != strong_ordering::equal)
                    return second_segment < 0;
                const auto third_segment{comperator.check(rl + R - L, ll, L)};
                if (third_segment != strong_ordering::equal)
                    return third_segment < 0;
                return true;
            } else {
                const auto first_segment{comperator.check(ll, rl, R)};
                if (first_segment != strong_ordering::equal)
                    return first_segment < 0;
                const auto second_segment{comperator.check(ll + R, ll, L - R)};
                if (second_segment != strong_ordering::equal)
                    return second_segment < 0;
                const auto third_segment{comperator.check(rl, ll + L - R, R)};
                if (third_segment != strong_ordering::equal)
                    return third_segment < 0;
                return false;
            }
        };
    }};
    unsigned N, K;
    cin >> N >> K;
    auto [minimum_S, prefix_lengths] {[N, &infinite_repeat_compare_from_comperator]{
        const auto [comperator, segments]{[N]{
            constexpr unsigned max_size{10};
            vector<string> A(max_size + 1);
            for (unsigned i{}; i < N; ++i) {
                string S;
                cin >> S;
                const auto L{size(S)};
                if (empty(A[L]))
                    A[L] = move(S);
                else
                    A[L] = min(A[L], move(S));
            }
            erase_if(A, [](const auto& s) { return empty(s); });
            string concatenated_str{};
            vector<pair<unsigned, unsigned>> segments;
            for (const auto& s : A) {
                segments.emplace_back(size(concatenated_str), size(concatenated_str) + size(s));
                concatenated_str += s;
            }
            return make_pair(string_segment_comperator{concatenated_str}, segments);
        }()};
        const auto compare_infinite_repeat{infinite_repeat_compare_from_comperator(comperator)};
        const auto &[L, R]{ranges::min(segments, compare_infinite_repeat)};
        vector<unsigned> prefix_lengths;
        for (const auto& [l, r] : segments)
            if (r + L <= R + l && comperator.check(l, L, r - l) == strong_ordering::equal)
                prefix_lengths.emplace_back(r - l);
        string minumum_S{comperator.str().substr(L, R - L)};
        return make_pair(minumum_S, prefix_lengths);
    }()};

    minimum_S += minimum_S;
    const string_segment_comperator comperator{minimum_S};
    const auto compare_infinite_repeat{infinite_repeat_compare_from_comperator(comperator)};
    vector<pair<unsigned, unsigned>> segments{};
    for (const auto& l : prefix_lengths) {
        while (!empty(segments) && compare_infinite_repeat(make_pair(segments.back().second, l), segments.back()))
            segments.pop_back();
        if (empty(segments))
            segments.emplace_back(l, l);
        else
            segments.emplace_back(segments.back().second, l);
    }
    const auto compare_partially_infinite_repeat{[&comperator](const auto& lhs, const auto& rhs) {
        const auto &[ll, lr]{lhs};
        const auto &[rl, rr]{rhs};
        const auto L{lr - ll}, R{rr - rl};
        if (L > R)
            return comperator.check(ll, rl, R) < 0;
        const auto first_segment{comperator.check(ll, rl, L)};
        if (first_segment != strong_ordering::equal)
            return first_segment < 0;
        const auto second_segment{comperator.check(rl, rl + L, R - L)};
        return second_segment < 0;
    }};
    unsigned ans{};
    for (unsigned i{}, j{1}; i < K; ++i) {
        while (j < size(segments) && compare_partially_infinite_repeat(segments[j], make_pair(0, ans)))
            ++j;
        if (j == size(segments)) {
            ans += segments[j - 1].second * (K - i);
            break;
        }
        ans += segments[j - 1].second;
    }
    for (unsigned i{}; i < ans; ++i)
        cout << minimum_S[i % size(minimum_S)];
    cout << endl;
    return 0;
}

posted:
last update: