結果

問題 No.515 典型LCP
コンテスト
ユーザー fine
提出日時 2019-11-01 02:18:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,006 bytes
コンパイル時間 2,006 ms
コンパイル使用メモリ 183,780 KB
実行使用メモリ 97,496 KB
最終ジャッジ日時 2024-09-14 22:14:28
合計ジャッジ時間 6,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SuffixArray {
    string str;
    vector<int> sa;
    vector<int> rank; // saの逆関数に相当

    SuffixArray() {}

    // O(N log N)
    SuffixArray(const string& s) : str(s) {
        if (str.empty()) return;

        int n = str.size();
        sa.resize(n, 0);
        rank.resize(n, 0);

        if (n == 1) return;

        // 長さ1のソート
        constexpr int CHAR_NUM = 256;
        vector<int> cnt(max(n, CHAR_NUM), 0);

        for (int i = 0; i < n; i++) {
            cnt[str[i]]++;
        }

        for (int i = 1; i < CHAR_NUM; i++) {
            cnt[i] += cnt[i - 1];
        }

        for (int i = 0; i < n; i++) {
            sa[--cnt[str[i]]] = i;
        }

        rank[sa[0]] = 0;
        int classes = 1;
        for (int i = 1; i < n; i++) {
            if (str[sa[i]] != str[sa[i - 1]]) classes++;
            rank[sa[i]] = classes - 1;
        }

        // 長さlen*2のソート
        int len;
        auto equal_class = [&](const int i, const int j) {
            if (rank[i] != rank[j]) return false;
            else {
                int ri = (i + len < n ? rank[i + len] : -1);
                int rj = (j + len < n ? rank[j + len] : -1);
                return ri == rj;
            }
        };

        vector<int> tmp_sa(n), tmp_rank(n);
        for (len = 1; len < n; len <<= 1) {
            fill(cnt.begin(), cnt.begin() + classes, 0);
            for (int i = 0; i < n; i++) {
                cnt[rank[sa[i]]]++;
            }

            for (int i = 1; i < classes; i++) {
                cnt[i] += cnt[i - 1];
            }

            for (int i = n - 1; i >= 0; i--) {
                if (sa[i] + len >= n) tmp_sa[i] = sa[i];
                if (sa[i] >= len) {
                    int s1 = sa[i] - len;
                    tmp_sa[--cnt[rank[s1]]] = s1;
                }
            }
            sa.swap(tmp_sa);

            tmp_rank[sa[0]] = 0;
            classes = 1;
            for (int i = 1; i < n; i++) {
                if (!equal_class(sa[i-1], sa[i])) classes++;
                tmp_rank[sa[i]] = classes - 1;
            }
            rank.swap(tmp_rank);
        }
    }

    int operator[](int idx) const {
        return sa[idx];
    }

    // 文字列s以上となる最小の接尾辞について、SAのindexを返す（無いならsa.size()を返す）
    int lower_bound(const string& s) const {
        int ng = -1, ok = sa.size();
        while (ok - ng > 1) {
            int mid = (ok + ng) >> 1;
            (str.compare(sa[mid], s.size(), s) < 0 ? ng : ok) = mid;
        }
        return ok;
    }

    // 文字列sが文字列strに含まれるならSAのindexを、無いなら-1を返す
    int find(const string& s) const {
        int idx = lower_bound(s);
        return ((idx < sa.size() && str.compare(sa[idx], s.size(), s) == 0) ? idx : -1);
    }

    // 文字列sが文字列strに含まれるか？
    bool contain(const string& s) const {
        return find(s) != -1;
    }
};

template <class SemiLattice>
struct SparseTable {
    using T = typename SemiLattice::T;

    int n;
    vector< vector<T> > table;
    vector<int> log_table;

    SparseTable() {}
    SparseTable(const vector<T>& v) {
        n = v.size();

        log_table.resize(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            log_table[i] = log_table[i >> 1] + 1;
        }

        table.resize(log_table[n] + 1, vector<T>(n));
        for (int i = 0; i < n; i++) {
            table[0][i] = v[i];
        }

        size_t sz = table.size();
        for (int i = 1; i < sz; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = SemiLattice::merge(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    //区間[l, r)に対するクエリに答える
    T query(int l, int r) {
        assert(l < r);
        int k = log_table[r - l];
        return SemiLattice::merge(table[k][l], table[k][r - (1 << k)]);
    }
};

//以下、SemiLatticeの例
template <class U = ll>
struct RMQSL {
    using T = U;
    static T merge(T a, T b) { return min(a, b); }
};

struct LongestCommonPrefixArray {
    vector<int> lcp;
    const SuffixArray& sa;
    SparseTable< RMQSL<int> > st;

    LongestCommonPrefixArray() : sa(SuffixArray()) {}
    LongestCommonPrefixArray(const SuffixArray& sa) : sa(sa) {
        const string& s = sa.str;
        const vector<int>& rank = sa.rank;
        int n = s.size();

        lcp.resize(n - 1);
        for (int i = 0, h = 0; i < n; i++) {
            if (h > 0) h--;
            if (rank[i] == 0) continue;

            for (int j = sa[rank[i] - 1]; j + h < n && i + h < n; h++) {
                if (s[j + h] != s[i + h]) break;
            }
            lcp[rank[i] - 1] = h;
        }

        st = SparseTable< RMQSL<int> >(lcp);
    }

    int operator[](int idx) const {
        return lcp[idx];
    }

    // sa.str.substr(i) と sa.str.substr(j) のLCPを求める
    int getLCP(int i, int j) {
        i = sa.rank[i], j = sa.rank[j];
        if (i > j) swap(i, j);
        return st.query(i, j);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string all_s = "";
    vector<int> ids(n), len(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ids[i] = all_s.size();
        len[i] = s.size();
        all_s += s;
    }

    SuffixArray sa(all_s);
    LongestCommonPrefixArray lcp(sa);

    int m;
    ll x, d;
    cin >> m >> x >> d;
    ll ans = 0;
    for (int k = 1; k <= m; k++) {
        ll i = (x / (n - 1)) + 1;
        ll j = (x % (n - 1)) + 1;
        if (i > j) swap(i, j);
        else j++;

        int min_len = min(len[i - 1], len[j - 1]);
        i = ids[i - 1];
        j = ids[j - 1];

        ans += min(min_len, lcp.getLCP(i, j));

        x = (x + d) % ((ll)n * (n - 1));
    }
    cout << ans << "\n";
    return 0;
}
0