結果

問題 No.515 典型LCP
ユーザー Min_25Min_25
提出日時 2017-05-06 11:33:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 498 ms / 1,000 ms
コード長 5,690 bytes
コンパイル時間 1,406 ms
コンパイル使用メモリ 108,732 KB
実行使用メモリ 73,244 KB
最終ジャッジ日時 2024-09-14 13:49:36
合計ジャッジ時間 5,863 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 498 ms
73,244 KB
testcase_01 AC 327 ms
72,700 KB
testcase_02 AC 178 ms
72,172 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 195 ms
72,732 KB
testcase_06 AC 193 ms
72,860 KB
testcase_07 AC 194 ms
72,812 KB
testcase_08 AC 221 ms
72,736 KB
testcase_09 AC 132 ms
72,180 KB
testcase_10 AC 133 ms
72,176 KB
testcase_11 AC 131 ms
72,180 KB
testcase_12 AC 134 ms
72,304 KB
testcase_13 AC 131 ms
72,172 KB
testcase_14 AC 75 ms
72,176 KB
testcase_15 AC 184 ms
72,736 KB
testcase_16 AC 190 ms
72,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>

#include <tuple>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

template <typename CharType>
struct InducedSort {
  using chr_t = CharType;
  using check_t = bool;

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

  static inline bool is_lms(const vector<check_t>& is_s, int i) {
    return is_s[i] && !is_s[i - 1];
  }

  InducedSort(const chr_t* str, int n, const int char_count=128) : str(str), size(n), sa(n, -1) {
    if (n <= 1) { sa[0] = 0; return; }
    if (n == 2) { sa[0] = 1; sa[1] = 0; return; }
    const auto is_s = scan_types();
    const auto offsets = calc_offsets(char_count);
    put_lms(is_s, offsets);
    scan_forward(is_s, offsets);
    scan_backward(is_s, offsets);
    calc_lms_pos(is_s, offsets);
    scan_forward(is_s, offsets);
    scan_backward(is_s, offsets);
  }

  void calc_lms_pos(const vector<check_t>& is_s, vector<int> offsets) {
    int next_size, next_char_count;
    tie(next_size, next_char_count) = convert(is_s);
    if (next_char_count < next_size) {
      auto res = InducedSort<int>(sa.data() + size - next_size, next_size, next_char_count);
      copy(res.sa.begin(), res.sa.end(), sa.begin());
    } else {
      rep(i, next_size) sa[sa[size - next_size + i]] = i;
    }
    int j = size - next_size;
    rep(i, 1, size) if (is_lms(is_s, i)) sa[j++] = i;
    rep(i, next_size) sa[i] = sa[size - next_size + sa[i]];
    rep(i, next_size, size) sa[i] = -1;
    for (int i = next_size - 1; i >= 0; --i) {
      int j = sa[i]; sa[i] = -1;
      sa[--offsets[str[j] + 1]] = j;
    }
  }

  pair<int, int> convert(const vector<check_t>& is_s) {
    int lms_count = 0;
    rep(i, size) if (sa[i] > 0 && !is_s[sa[i] - 1] && is_s[sa[i]]) sa[lms_count++] = sa[i];
    rep(i, lms_count, size) sa[i] = -1;
    int char_count = 0;
    sa[lms_count + (sa[0] >> 1)] = char_count++;
    rep(i, 1, lms_count) {
      int prev = sa[i - 1], curr = sa[i];
      for (int ofs = 0; ; ++ofs) {
        if (str[curr + ofs] != str[prev + ofs] || is_s[curr + ofs] != is_s[prev + ofs]) {
          char_count++; break;
        } else if (ofs > 0 && (is_lms(is_s, curr + ofs) || is_lms(is_s, prev + ofs))) {
          break;
        }
      }
      sa[lms_count + (curr >> 1)] = char_count - 1;
    }
    for (int i = size - 1, tail = i; i >= lms_count; --i) if (sa[i] >= 0) sa[tail--] = sa[i];
    return {lms_count, char_count};
  }
  void scan_forward(const vector<check_t>& is_s, vector<int> offsets) {
    rep(i, size) if (sa[i] >= 1 && !is_s[sa[i] - 1]) sa[offsets[str[sa[i] - 1]]++] = sa[i] - 1;
  }
  void scan_backward(const vector<check_t>& is_s, vector<int> offsets) {
    for (int i = size - 1; i >= 0; --i) if (sa[i] >= 1 && is_s[sa[i] - 1]) sa[--offsets[str[sa[i] - 1] + 1]] = sa[i] - 1;
  }
  void put_lms(const vector<check_t>& is_s, vector<int> offsets) {
    rep(i, 1, size) if (is_lms(is_s, i)) sa[--offsets[str[i] + 1]] = i;
  }
  vector<int> calc_offsets(int char_count) {
    vector<int> ret(char_count + 1, 0);
    rep(i, size) ret[int(str[i]) + 1] += 1;
    rep(i, 1, char_count + 1) ret[i] += ret[i - 1];
    return ret;
  }
  vector<check_t> scan_types() {
    vector<check_t> is_s(size);
    is_s.back() = 1;
    for (int i = size - 2; i >= 0; --i) is_s[i] = (str[i] < str[i + 1]) || (str[i] == str[i + 1] && is_s[i + 1]);
    return is_s;
  }
  pair< vector<int>, vector<int> > calc_lcp() {
    vector<int> lcp(size);
    vector<int> rank(size);
    rep(i, size) rank[sa[i]] = i;
    int k = 0;
    rep(i, size - 1) {
      int j = sa[rank[i] - 1];
      if (k) --k;
      while (i + k < size && j + k < size && str[i + k] == str[j + k]) ++k;
      lcp[rank[i] - 1] = k;
    }
    return {lcp, rank};
  }
  const chr_t* str;
  int size;
  vector<int> sa;
};

void solve() {
  int N;
  while (~scanf("%d", &N)) {
    static char buff[1000010];
    static int offsets[100010];
    static int tab[20][800010];

    int ofs = 0;
    rep(i, N) {
      scanf("%s", buff + ofs);
      offsets[i] = ofs;
      ofs += strlen(buff + ofs);
    }
    offsets[N] = ofs;
    buff[ofs++] = '\0';
    auto sa = InducedSort<char>(buff, ofs);
    auto p = sa.calc_lcp();
    auto& lcp = p.first, &rank = p.second;

    int size = lcp.size(), k = __lg(size);
    rep(i, size) tab[0][i] = lcp[i];
    rep(t, 1, k + 1) {
      int l = 1 << (t - 1);
      rep(i, 0, size - 2 * l + 1) tab[t][i] = min(tab[t - 1][i], tab[t - 1][i + l]);
    }

    int M; i64 x, d; scanf("%d %lld %lld", &M, &x, &d);
    const i64 N2 = i64(N) * (N - 1);

    i64 ans = 0;
    rep(_, M) {
      int i = x / (N - 1), j = x % (N - 1);
      if (i > j) swap(i, j);
      else ++j;
      int len = min(offsets[i + 1] - offsets[i], offsets[j + 1] - offsets[j]);
      int p1 = rank[offsets[i]], p2 = rank[offsets[j]];
      if (p2 < p1) swap(p1, p2);
      int l = __lg(p2 - p1);
      ans += min(len, min(tab[l][p1], tab[l][p2 - (1 << l)]));
      if ((x += d) >= N2) x -= N2;
    }
    printf("%lld\n", ans);
  }
}

int main() {
  auto beg = clock();
  solve();
  auto end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
}
0