#425715 (C++14) No.515 典型LCP

提出ソース
結果

問題	No.515 典型LCP
ユーザー	shugo256
提出日時	2020-02-03 23:44:56
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,412 bytes
コンパイル時間	1,627 ms
コンパイル使用メモリ	100,952 KB
実行使用メモリ	47,792 KB
最終ジャッジ日時	2023-10-19 15:31:56
合計ジャッジ時間	11,835 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	WA	-
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

#define isLMS(i) (isL[(i)-1] && !isL[i])
#define LIMIT 200000

template <typename T>
class SuffixArray {
    vector<T> s;
    const size_t len,
                 limit;  // lenは配列長 limitは配列に登場する文字/数字の種類数
    vector<size_t> bin,  // 頭文字の各アルファベットの出現回数の累積和
                   cnt,  // どのアルファベットから始まるものをいくつsaに割り当てたか
                   lms,  // LMSのインデックスを格納する配列
                   isL,  // s[i]がL型なら1 S型なら0
                   sa;   // sのsuffix arrayをインデックスで格納する配列

public:
    vector<size_t> rank; // s[i:]が辞書順で何番目のsuffixか(saの逆写像)、番兵も

    // Tが整数の時よう
    SuffixArray(vector<T> s, size_t limit=LIMIT)
     : s(s),
       len(s.size()),
       limit(limit),
       bin(limit+1, 0),
       cnt(limit+1, 0),
       isL(len+1),
       sa(len+1),
       rank(len+1) {
           (this->s).push_back(0); // 末尾に番兵の追加
           lms.reserve(len/2);     // lmsの領域の確保
           sa_is();                // SAの構築
            for (size_t i=0; i<=len; i++)
                rank[sa[i]] = i; // rankの計算
    } 

    // Tがcharの時用
    SuffixArray(string s, size_t limit=256) : SuffixArray(vector<char>(s.begin(), s.end()), limit) {}

    // LCP(高さ配列、蟻本p339)を計算する
    // lcp[i] = sa[i]とsa[i+1]の先頭何文字が一致しているか
    // このlcpをRange Minimum Queryに載せれば任意のi jに対してlcpが計算可能
    vector<int> lcp;

    void construct_lcp() {
        lcp.resize(len);
        size_t h = 0;
        for (size_t i=0; i<len; i++) {
            size_t j = sa[rank[i] - 1];
            if (h > 0) h--;
            for ( ; i+h<len && j+h<len && s[i+h] == s[j+h]; h++);

            lcp[rank[i] - 1] = (int)h;
        }
    }

    auto begin() { return sa.begin(); }
    auto end()   { return sa.end(); }

    template <typename ID>
    int operator[](ID i) { return (int)sa[(size_t)i]; }

private:

    //SA-IS法によりSuffixArrayを構築する
    void sa_is() {
        isL[len] = false;
        bin[1] = 1;
        for (size_t i=len; i>0; i--) {
            isL[i-1] = (s[i-1] == s[i]) ? isL[i] : (s[i-1] > s[i]);
            bin[(size_t)s[i-1]+1]++;
            if (isLMS(i))
                lms.push_back(i);
        }

        vector<size_t> aligned(lms); // あとでlmsは色々並べ替えるが、ここに今の整列した状態を保存しておく
        reverse(aligned.begin(), aligned.end()); // 降順になっているのをひっくり返して昇順にする

        for (size_t i=0; i<limit; i++) bin[i+1] += bin[i]; // 累積和

        induced_sort(); // 1回目のinduced sort

        fill(sa.begin(), sa.end(), 0); // saにLMS部分文字列の順位を格納する
        size_t n = 0, lmslen = lms.size();

        // 辞書順で隣り合うLMSについて一致しているかどうか調べる(たかだかn回の比較)
        for (auto itr=lms.begin(); itr+1!=lms.end(); itr++) {
            size_t i = *itr, j = *(itr+1);
            for (size_t d=0; i+d <= len && j+d <= len; d++) {
                if (s[i+d] != s[j+d] || isLMS(i+d) != isLMS(j+d)) {
                    n++;
                    break;
                } else if (d > 0 && (isLMS(i+d) || isLMS(j+d)))
                    break;
            }
            sa[j] = n;
        }

        if (n < lmslen-1) {
            vector<size_t> next_s(lmslen-1);
            for (size_t i=0; i<lmslen-1; i++) { // alignedはここで使うために用意した
                next_s[i] = sa[aligned[i]];
                sa[aligned[i]] = 0; // saはまた0リセット
            }

            // sa-isを再帰的に用いる
            SuffixArray<size_t> next(next_s, n+1);

            for (size_t i=0; i<lmslen-1; i++)
                lms[i] = aligned[(size_t)next[lmslen-1-i]];
            lms[lmslen-1] = len;
        } else {
            for (auto i:aligned) 
                sa[i] = 0; // saを0リセット
        }

        fill(cnt.begin(), cnt.end(), 0);

        induced_sort();
    }

    // induced sortの3ステップを行う
    void induced_sort() {

        // step1:LMSをひとまず書き込んでいく
        for (auto i:lms) {
            size_t c = (size_t)s[i];
            cnt[c+1]++;
            sa[bin[c+1] - cnt[c+1]] = i;
        }

        fill(cnt.begin(), cnt.end(), 0);

        //step2:L型のsuffixを埋めていく
        for (auto i:sa) {
            if (i == 0 || !isL[i-1]) continue;
            size_t c = (size_t)s[i-1];
            sa[bin[c] + cnt[c]] = i-1;
            cnt[c]++;
        } 

        fill(cnt.begin(), cnt.end(), 0);
        auto lmsitr = lms.rbegin();

        //step3:S型のsuffixを埋めていく
        for (auto itr=sa.rbegin(); itr!=sa.rend(); itr++) {
            size_t i = *itr;
            if (i == 0) continue;
            if (isLMS(i)) { // ここでlmsをsaに出てくる順に並べ替えておく
                *lmsitr = i;
                lmsitr++;
            }
            if (isL[i-1]) continue;
            size_t c = (size_t)s[i-1];
            cnt[c]++;
            sa[bin[c+1] - cnt[c]] = i-1;
        }
    }
};

// 番兵を0としているので、sの要素は全部正にする(or番兵を変える)

#include <functional>
#include <limits>

#define ASSIGN_I [](T &ival, T x) { ival = x; }  // i番目にxを代入(点更新のデフォルト)

template <typename T>
class SegmentTree {
    int n;                       // 葉の数
    T def;                 // 初期値 && 単位元
    vector<T> tree;              // 本体 

    using op_func_t = function<T(T, T)>;
    using up_func_t = function<void(T&, T)>;

    op_func_t op_func; // 区間クエリで使う処理
    up_func_t up_func; // 点更新で使う処理 ただの変更の他、i番目にxをたすみたいなこともできる

    // 区間[a, b)の総和(と言うか総operation(は？))
    // ノードk=[l, r)を見ている
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def;            // 全く交差しない場合
        if (a <= l && r <= b) return tree[(size_t)k]; // 完全に包含される場合
        T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2),
          vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
        return op_func(vl, vr);
    }

  public:
    SegmentTree(int _n, T _def, op_func_t _op_func, up_func_t _up_func = ASSIGN_I)
        : def(_def), op_func(_op_func), up_func(_up_func)  {
        n = 1;
        while (n < _n) n <<= 1;
        tree = vector<T>((size_t)(2*n - 1), def);
    }

    //よく使うやつら min, max, sum
    SegmentTree(int _n, T _def, string mode, up_func_t _up_func = ASSIGN_I)
        : SegmentTree(
            _n, 
            _def,
            mode == "max" ? [](T l, T r) { return max(l, r); } :
           (mode == "min" ? [](T l, T r) { return min(l, r); } :
                            [](T l, T r) { return l + r; }), // sum
            _up_func
        ) {}

    SegmentTree(int _n, string mode, up_func_t _up_func = ASSIGN_I)
        : SegmentTree(
            _n, 
            mode == "max" ? numeric_limits<T>::lowest() : 
           (mode == "min" ? numeric_limits<T>::max() :
                            0), // sum
            mode,
            _up_func
        ) {}

    template <typename ID>
    void update(ID i, T x) {
        i += (ID)n - 1;
        up_func(tree[(size_t)i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            tree[(size_t)i] = op_func(tree[(size_t)(i * 2 + 1)], tree[(size_t)(i * 2 + 2)]);
        }
    }

    template <typename ID1, typename ID2>
    T query(ID1 a, ID2 b) { return _query((int)a, (int)b, 0, 0, n); }

    void print_tree() {
        size_t next = 0, size = (size_t)(2 * n - 1);
        for (size_t i=0; i<size; i++) {
            cout << tree[i];
            if (i == next) {
                cout << '\n';
                next = (next + 1) * 2;
            } else 
                cout << string(size * 2 / (next+2), ' ');
        }
    }

    auto begin() { return tree.begin() + n - 1; }
    auto end() { return tree.end(); }

    T operator[](int i) { return tree[ (size_t)(i + n - 1) ]; }
};
/*
コンストラクタ
SegmentTree(n, def, op_func, [up_func])
SegmentTree(n, def, mode, [up_func])
SegmentTree(n, mode, [up_func])
*/

int main() {
    ll n;
    cin >> n;
    string s, si;
    int tops[n+1];
    for (int i=0; i<n; i++) {
        cin >> si;
        tops[i] = s.size();
        s += si;
    }
    tops[n] = s.size();
    SuffixArray<char> sa(s);
    sa.construct_lcp();
    SegmentTree<int> sgt(s.size(), "min");
    int l=0;
    for (auto &lcpl:sa.lcp) sgt.update(l++, lcpl);
    int m;
    ll x, d, ans = 0;
    cin >> m >> x >> d;
    for (int k=0; k<m; k++) {
        int i = (x / (n-1)),
            j = (x % (n-1));
        if (i > j) swap(i, j);
        else j++;
        x = (x + d) % (n * (n-1));

        ans += min({sgt.query(sa.rank[tops[i]], sa.rank[tops[j]]), tops[i+1] - tops[i], tops[j+1] - tops[j]});    }
    cout << ans << '\n';
    return 0;
}
yukicoder

結果

テストケース

ソースコード
