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

提出ソース
結果

問題	No.515 典型LCP
コンテスト
ユーザー	furuya1223
提出日時	2019-10-13 12:16:38
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	17,325 bytes
コンパイル時間	2,278 ms
コンパイル使用メモリ	141,972 KB
実行使用メモリ	32,792 KB
最終ジャッジ日時	2024-12-14 16:24:28
合計ジャッジ時間	16,040 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	WA * 13 TLE * 2
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/timeb.h>
#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define chmin(mi, val) mi = min(mi, val)
#define chmax(ma, val) ma = max(ma, val)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFR INT_MAX
#define INFL (long long)(4e18)
#define INFLR LLONG_MAX
#define EPS (1e-10)
//#define MOD 1000000007
#define MOD 998244353
#define PI 3.141592653589793238
#define RMAX 4294967295

using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;
using Pi = pair<int, int>;
using vPi = vector<Pi>;
using vvPi = vector<vector<Pi>>;
using vvvPi = vector<vector<vector<Pi>>>;
using vvvvPi = vector<vector<vector<vector<Pi>>>>;
using Pll = pair<ll, ll>;
using vPll = vector<Pll>;
using Pd = pair<double, double>;
using vPd = vector<Pd>;
template <class T>
using vec = vector<T>;
template <class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
using Comp = complex<double>;

// vvvvvvvvvvvvvvvvvvvvvvv debug output vvvvvvvvvvvvvvvvvvvvvvv
// vector input
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// deque
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// multiset
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}

#define DUMPOUT cerr

void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG_
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

// ^^^^^^^^^^^^^^^^^^^^^^^ debug output ^^^^^^^^^^^^^^^^^^^^^^^

string YN(bool y, int id = 0) {
    if (id) cout << id;
    return (y ? "YES" : "NO");
}
string yn(bool y, int id = 0) {
    if (id) cout << id;
    return (y ? "Yes" : "No");
}
string ON(bool y, int id = 0) {
    if (id) cout << id;
    return (y ? "OK" : "NG");
}

int dir4[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
int dir8[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0},
                  {1, 0},   {-1, 1}, {0, 1},  {1, 1}};
char dirchar[4] = {'<', '^', '>', 'v'};

// [a,b)
int irand(int a, int b) {
    static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
    uniform_int_distribution<int> dist(a, b - 1);
    return dist(Rand);
}

// [a,b)
double drand(int a, int b) {
    static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
    uniform_real_distribution<double> dist(a, b);
    return dist(Rand);
}

// https://qiita.com/IgnorantCoder/items/3101d6276e9bdddf872c
template <typename A, typename F>
inline auto transform(const A &v, F &&f) {
    using result_type =
        decltype(std::declval<F>()(std::declval<typename A::value_type>()));
    vector<result_type> y(v.size());
    std::transform(std::cbegin(v), std::cend(v), std::begin(y), f);
    return y;
}

// generate vector which has multiple dimension
template <class T>
vector<T> make_v(size_t size, const T &init) {
    return vector<T>(size, init);
}
template <class... Ts>
auto make_v(size_t size, Ts... rest) {
    return vector<decltype(make_v(rest...))>(size, make_v(rest...));
}

template <typename T>
T Max(vector<T> a) {
    return *max_element(all(a));
}
template <typename T>
T Min(vector<T> a) {
    return *min_element(all(a));
}
template <typename T>
T Sum(vector<T> a) {
    return accumulate(all(a), (T)0);
}

// for counting using map
template <typename T>
void Add(map<T, int> &m, T item) {
    if (m.find(item) == m.end()) {
        m[item] = 1;
    } else {
        m[item]++;
    }
}

// for counting using map
template <typename T>
void Erase(map<T, int> &m, T item) {
    if (m.find(item) == m.end()) {
    } else {
        if (m[item] == 1) {
            m.erase(item);
        } else {
            m[item]--;
        }
    }
}

// get method for map with default value
template <typename T, typename U>
U Get(map<T, U> m, T key, U def) {
    if (m.find(key) == m.end()) {
        return def;
    } else {
        return m[key];
    }
}

template <typename T>
inline bool Contains(const set<T> &t, const T &key) {
    return t.find(key) != t.end();
}

template <typename T, typename U>
inline bool Contains(const map<T, U> &t, const T &key) {
    return t.find(key) != t.end();
}

template <class T>
struct Edge {
    int from, to;
    T cost;
    bool operator<(Edge e) {
        return cost < e.cost;
    }
    Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
};

template <class T>
ostream &operator<<(ostream &os, Edge<T> &edge) {
    os << "(" << edge.from << "->" << edge.to << ":" << edge.cost << ")";
    return os;
}
template <class T = int>
class Graph {
    int n;
    bool directed;
    vector<vector<Edge<T>>> edges;

  public:
    Graph(int n, bool directed)
        : n(n), directed(directed), edges(vector<vector<Edge<T>>>(n)) {}

    void add_edge(int s, int t, T cost) {
        edges[s].emplace_back(s, t, cost);
        if (!directed) {
            edges[t].emplace_back(t, s, cost);
        }
    }
    Graph() {}

    vector<Edge<T>> &operator[](size_t i) {
        return edges[i];
    }

    int size() const {
        return n;
    }
};

//======================================================
template <class T>
class SegTree {
    int n;                       // 葉の数
    vector<T> data;              // データを格納するvector
    T def;                       // 初期値かつ単位元
    function<T(T, T)> operation; // 区間クエリで使う処理
    function<T(T, T)> update;    // 点更新で使う処理

    // 区間[a,b)の総和。ノード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 data[k]; // a,l,r,bの順で完全に含まれる
        else {
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
            return operation(c1, c2);
        }
    }

  public:
    // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
    // _update:更新関数
    SegTree(size_t _n, T _def, function<T(T, T)> _operation,
            function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        data = vector<T>(2 * n - 1, def);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    // [a, b)の区間クエリを実行
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    // 添字でアクセス
    T operator[](int i) {
        return data[i + n - 1];
    }
};

class SuffixArray {
    static const int L_type = 0, S_type = 1, LMS_type = 2;

    static void induce_sort(const vector<int> &v, vector<int> &sa,
                            const vector<int> &type, vector<int> start,
                            vector<int> end) {
        int len = sa.size();
        // L-type の要素を各バケットに前から詰める
        for (int i = 0; i < len; i++) {
            if (sa[i] == -1) continue;
            if (sa[i] - 1 >= 0 && type[sa[i] - 1] == L_type) {
                sa[start[v[sa[i] - 1]]++] = sa[i] - 1;
            }
            if (i != 0 && type[sa[i]] == LMS_type) {
                sa[i] = -1;
            }
        }
        // S-type の要素を各バケットに後ろから詰める
        for (int i = len - 1; i >= 0; i--) {
            if (sa[i] == -1) continue;
            if (sa[i] - 1 >= 0 && type[sa[i] - 1] != L_type) {
                sa[--end[v[sa[i] - 1]]] = sa[i] - 1;
            }
        }
    }

  public:
    vector<int> str; // 入力配列
    vector<int> suffix_array;
    vector<int> order; // SA における添字: order[suffix_array[i]] = i
    vector<int> lpc;   // SA[i], SA[i+1] の LPC 長

    SuffixArray(vector<int> &v, int char_num) {
        str = v;
        suffix_array = SA_IS(str, char_num);
    }

    SuffixArray(const string &s) {
        str.resize(s.size());
        for (int i = 0; i < s.size(); i++) {
            str[i] = s[i] - 'a' + 1;
        }
        suffix_array = SA_IS(str, 26);
    }

    static vector<int> SA_IS(vector<int> &v, int char_num) {
        if (v.size() == 1) {
            // 再帰の終わり
            return vector<int>(1, 0);
        }
        v.push_back(0);
        char_num++;

        int len = v.size();
        vector<int> tmp_sa(len, -1);
        vector<int> type(len);
        vector<int> start(char_num), end(char_num); // バケットiの注目範囲
        vector<int> LMS;                            // LMS の開始位置
        vector<int> LMS_order(len, -1); // LMS のソート順序（非 LMS では -1）

        // type の判定
        type.back() = S_type;
        end[0] = 1;
        for (int i = len - 2; i >= 0; i--) {
            if (v[i] > v[i + 1]) {
                type[i] = L_type;
                if (type[i + 1] == S_type) {
                    LMS.push_back(i + 1);
                    type[i + 1] = LMS_type;
                    LMS_order[i + 1] = 0;
                }
            } else if (v[i] < v[i + 1]) {
                type[i] = S_type;
            } else {
                type[i] = type[i + 1];
            }
            end[v[i]]++;
        }
        // start, end の計算
        start[0] = 0;
        for (int i = 1; i < char_num; i++) {
            end[i] += end[i - 1];
            start[i] = end[i - 1];
        }
        // Induce Sort の準備
        for (int i = 0; i < len; i++) {
            if (LMS_order[i] != -1) {
                tmp_sa[--end[v[i]]] = i;
            }
        }
        // end の復元
        for (int i = 0; i < char_num - 1; i++) {
            end[i] = start[i + 1];
        }
        end[char_num - 1] = len;

        // Induce Sort で LMS-substring をソートする
        induce_sort(v, tmp_sa, type, start, end);

        // LMS のみからなる数列を作成する

        // LMS のソート順序を調べる
        int counter = 0;
        int prev_lms = -1; // 1 つ前の LMS の先頭
        for (int i = 0; i < len; i++) {
            if (LMS_order[tmp_sa[i]] != -1) {
                LMS_order[tmp_sa[i]] = ++counter;
                if (prev_lms == -1) {
                    prev_lms = tmp_sa[i];
                    continue;
                }
                // 1 つ前の LMS と同じか判定
                bool different = false;
                for (int j = 0; j < len; j++) {
                    // j 文字目（prev_lms+j と tmp_sa[i]+j）をチェック
                    if (prev_lms + j >= len || tmp_sa[i] + j >= len ||
                        (j != 0 && (LMS_order[prev_lms + j] != -1 ||
                                    LMS_order[tmp_sa[i] + j] != -1))) {
                        break;
                    }
                    if (v[prev_lms + j] != v[tmp_sa[i] + j]) {
                        different = true;
                        break;
                    }
                }
                if (!different) {
                    LMS_order[tmp_sa[i]] = --counter;
                }
                prev_lms = tmp_sa[i];
            }
        }
        vector<int> new_v; // v での出現順に LMS-substring の順位が並ぶ
        vector<int> position(len, 0); // 各 LMS の開始位置
        counter = 0;
        for (int i = 0; i < len; i++) {
            if (LMS_order[i] != -1) {
                new_v.push_back(LMS_order[i]);
                position[counter++] = i;
            }
        }

        // SA-IS を再帰適用して LMS をソートする
        vector<int> lms_sa = SA_IS(new_v, new_v.size());

        // Induce Sort の準備
        fill(tmp_sa.begin(), tmp_sa.end(), -1);
        for (int i = lms_sa.size() - 1; i >= 0; i--) {
            if (LMS_order[position[lms_sa[i]]] != -1) {
                tmp_sa[--end[v[position[lms_sa[i]]]]] = position[lms_sa[i]];
            }
        }
        // end の復元
        for (int i = 0; i < char_num - 1; i++) {
            end[i] = start[i + 1];
        }
        end[char_num - 1] = len;

        // Induce Sort で saffix array を完成させる
        induce_sort(v, tmp_sa, type, start, end);

        tmp_sa.erase(tmp_sa.begin()); // 先頭の空文字列を削除
        v.pop_back();                 // 末尾に足した 0 を削除

        return tmp_sa;
    }

    void calc_lpc() {
        if (lpc.size() != 0) return;

        int len = str.size();
        lpc.resize(len);
        order.resize(len);
        for (int i = 0; i < len; i++) {
            order[suffix_array[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < len; i++) {
            // str[i..] と SA でその前にある接尾辞の LPC を求める
            if (order[i] == 0) {
                h = 0;
                continue;
            }
            int j = suffix_array[order[i] - 1];
            if (h > 0) h--;
            while (i + h < len && j + h < len) {
                if (str[i + h] != str[j + h]) break;
                h++;
            }
            lpc[order[i] - 1] = h;
        }
    }
};

int main() {
    ll N;
    cin >> N;
    string S;
    vi start(N);
    rep(i, N) {
        start[i] = S.size();
        string s;
        cin >> s;
        S += s;
    }
    dump(S);
    dump(start);
    ll M, x, d;
    cin >> M >> x >> d;

    SuffixArray SA(S);
    dump(SA.suffix_array);
    SA.calc_lpc();
    dump(SA.lpc);

    SegTree<int> st(SA.lpc.size(), INF, [](int a, int b) { return min(a, b); },
                    [](int a, int b) { return b; });
    rep(i, SA.lpc.size()) {
        st.change(i, SA.lpc[i]);
    }

    ll ans = 0;
    rep(k, M) {
        int i = (x / (N - 1)) + 1;
        int j = (x % (N - 1)) + 1;
        if (i > j)
            swap(i, j);
        else
            j++;
        x = (x + d) % (N * (N - 1));

        i--, j--;
        dump(i, j, start[i], start[j], SA.order[start[i]], SA.order[start[j]]);
        ans += st.query(SA.order[start[i]], SA.order[start[j]]);
    }

    cout << ans << endl;

    return 0;
}
yukicoder

結果

ソースコード
