結果

問題 No.464 PPAP
ユーザー koba-e964koba-e964
提出日時 2016-12-15 23:18:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 521 ms / 2,000 ms
コード長 3,802 bytes
コンパイル時間 1,325 ms
コンパイル使用メモリ 76,124 KB
実行使用メモリ 100,548 KB
最終ジャッジ日時 2023-08-20 08:02:48
合計ジャッジ時間 6,193 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 18 ms
22,836 KB
testcase_08 AC 18 ms
22,752 KB
testcase_09 AC 20 ms
22,744 KB
testcase_10 AC 417 ms
76,376 KB
testcase_11 AC 255 ms
65,348 KB
testcase_12 AC 394 ms
79,208 KB
testcase_13 AC 414 ms
100,548 KB
testcase_14 AC 413 ms
100,548 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,384 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,384 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 2 ms
4,384 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 521 ms
100,500 KB
testcase_24 AC 490 ms
100,508 KB
testcase_25 AC 451 ms
100,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

/*
 * Suffix Array.
 * Required Headers: algorithm, cassert, string, vector
 * Verified by: http://arc050.contest.atcoder.jp/submissions/818745
 * Reference: http://mayokoex.hatenablog.com/entry/2016/04/03/145845
 */
struct compare_sa {
  const std::vector<int> &rank;
  int n, k;
  compare_sa(const std::vector<int> &rank, int n, int k) : rank(rank), n(n), k(k) {}
  bool operator () (int i, int j) {
    if (rank[i] != rank[j]) {
      return rank[i] < rank[j];
    }
    int ri = i + k <= n ? rank[i + k] : -1;
    int rj = j + k <= n ? rank[j + k] : -1;
    return ri < rj;
  }
};

std::vector<int> create_sa(const std::string& s) {
  int n = s.length();
  std::vector<int> sa(n + 1, -1);
  std::vector<int> rank(n + 1, -1);
  std::vector<int> tmp(n + 1, -1);
  
  for (int i = 0; i <= n; ++i) {
    sa[i] = i;
    rank[i] = i < n ? s[i] : -1;
  }
  
  for (int k = 1; k <= n; k *= 2) {
    compare_sa cp = compare_sa(rank, n, k);
    std::sort(sa.begin(), sa.begin() + n + 1, cp);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; ++i) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    for (int i = 0; i <= n; ++i) {
      rank[i] = tmp[i];
    }
  }
  return sa;
}

std::vector<int> create_lcp(const std::string &s, const std::vector<int> &sa) {
  int n = s.length();
  std::vector<int> rank(n + 1);
  std::vector<int> lcp(n, -1);
  for (int i = 0; i <= n; ++i) {
    rank[sa[i]] = i;
  }
  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; ++i) {
    int j = sa[rank[i] - 1];
    h = std::max(0, h - 1);
    for (; j + h < n && i + h < n; ++h) {
      if (s[j + h] != s[i + h]) {
	break;
      }
    }
    lcp[rank[i] - 1] = h;
  }
  return lcp;
}

std::vector<std::vector<int> > create_sparse_table(int n, const std::vector<int> &lcp) {
  int h = 1;
  while ((1 << h) < n) {
    ++h;
  }
  std::vector<std::vector<int> > st(h + 1, std::vector<int>(n));

  for (int i = 0; i < n; ++i) {
    st[0][i] = lcp[i];
  }
  for (int j = 1; j <= h; ++j) {
    for (int i = 0; i <= n - (1 << j); ++i) {
      st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j-1))]);
    }
  }
  return st;
}

int top_bit(int t) {
  for (int i = 31; i >= 0; --i) {
    if ((1 << i) & t) {
      return i;
    }
  }
  assert (0);
}

int get_lcp(const std::vector<std::vector<int> > &st, int f, int s) {
  if (f > s) {
    std::swap(f, s);
  }
  assert (f < s);
  int diff = top_bit(s - f);
  return std::min(st[diff][f], st[diff][s - (1 << diff)]);
}



const int N = 5001;
int pal[N][N];
int pal2[N];

int main(void){
  string s;
  cin >> s;
  string s_rev = s;
  reverse(s_rev.begin(), s_rev.end());
  int n = s.length();
  string t = s + "$" + s_rev;
  VI sa = create_sa(t);
  VI sa_inv(sa.size());
  REP(i, 0, sa.size()) {
    sa_inv[sa[i]] = i;
  }
  VI lcp = create_lcp(t, sa);
  vector<VI> spt = create_sparse_table(2 * n + 1, lcp);
  REP(i, 0, n) {
    REP(j, i, n) {
      int idx1 = sa_inv[i];
      int idx2 = sa_inv[n + 1 + (n - 1 - j)];
      int comm_len = get_lcp(spt, idx1, idx2);
      if (0) {
	cerr << "idx1=" << idx1 << ", idx2=" << idx2 << endl;
	cerr << "lcp(s[" << i << "..], s[.." << j << "].rev) = "
	     << comm_len;
	if (comm_len >= j - i + 1) {
	  cerr << " pal";
	}
	cerr << endl;
      }
      pal[i][j] = comm_len >= j - i + 1;
    }
  }
  REP(i, 0, n) {
    REP(j, 0, n) {
      pal2[j] += pal[0][i] * pal[i + 1][j];
    }
  }
  ll tot = 0;
  REP(i, 0, n) {
    REP(j, i + 2, n) {
      tot += (ll)pal2[i] * pal[j][n - 1];
    }
  }
  cout << tot << endl;
}
0