#685598 (Lua) No.464 PPAP

提出ソース

結果

問題	No.464 PPAP
ユーザー	👑 obakyan
提出日時	2021-08-03 22:48:54
言語	Lua (LuaJit 2.1.1696795921)
結果	AC
実行時間	151 ms / 2,000 ms
コード長	10,380 bytes
コンパイル時間	258 ms
コンパイル使用メモリ	5,232 KB
実行使用メモリ	4,356 KB
最終ジャッジ日時	2023-10-14 21:11:21
合計ジャッジ時間	1,762 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,352 KB
testcase_03	AC	1 ms 4,352 KB
testcase_04	AC	3 ms 4,352 KB
testcase_05	AC	3 ms 4,348 KB
testcase_06	AC	3 ms 4,352 KB
testcase_07	AC	10 ms 4,352 KB
testcase_08	AC	6 ms 4,352 KB
testcase_09	AC	4 ms 4,356 KB
testcase_10	AC	151 ms 4,352 KB
testcase_11	AC	41 ms 4,352 KB
testcase_12	AC	65 ms 4,348 KB
testcase_13	AC	10 ms 4,352 KB
testcase_14	AC	12 ms 4,352 KB
testcase_15	AC	2 ms 4,352 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	3 ms 4,352 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	3 ms 4,352 KB
testcase_20	AC	3 ms 4,348 KB
testcase_21	AC	3 ms 4,352 KB
testcase_22	AC	3 ms 4,352 KB
testcase_23	AC	12 ms 4,348 KB
testcase_24	AC	12 ms 4,348 KB
testcase_25	AC	12 ms 4,356 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

local mfl, mce = math.floor, math.ceil
local mmi, mma = math.min, math.max
local bls, brs = bit.lshift, bit.rshift
local SegTree = {}
SegTree.updateAll = function(self)
  for i = self.stagenum - 1, 1, -1 do
    local cnt = bls(1, i - 1)
    for j = 1, cnt do
      self.stage[i][j] = self.func(self.stage[i + 1][j * 2 - 1], self.stage[i + 1][j * 2])
    end
  end
end
SegTree.create = function(self, n, func, emptyvalue)
  self.func, self.emptyvalue = func, emptyvalue
  local stagenum, mul = 1, 1
  self.stage = {{}}
  while mul < n do
    mul, stagenum = mul * 2, stagenum + 1
    self.stage[stagenum] = {}
  end
  self.stagenum = stagenum
  self.left_stage = {}
  for i = 1, n do
    local sp, sz = 1, bls(1, stagenum - 1)
    while(i - 1) % sz ~= 0 do
      sp, sz = sp + 1, brs(sz, 1)
    end
    self.left_stage[i] = sp
  end
  self.sz_stage = {}
  local tmp, sp = 1, stagenum
  for i = 1, n do
    if tmp * 2 == i then tmp, sp = tmp * 2, sp - 1 end
    self.sz_stage[i] = sp
  end
  for i = 1, mul do self.stage[stagenum][i] = emptyvalue end
  self:updateAll()
end
SegTree.getRange = function(self, left, right)
  if left == right then return self.stage[self.stagenum][left] end
  local stagenum = self.stagenum
  local ret = self.emptyvalue
  while left <= right do
    local stage = mma(self.left_stage[left], self.sz_stage[right - left + 1])
    local sz = bls(1, stagenum - stage)
    ret = self.func(ret, self.stage[stage][1 + brs(left - 1, stagenum - stage)])
    left = left + sz
  end
  return ret
end
SegTree.update = function(self, idx)
  for i = self.stagenum - 1, 1, -1 do
    local dst = brs(idx + 1, 1)
    local rem = dst * 4 - 1 - idx
    self.stage[i][dst] = self.func(self.stage[i + 1][idx], self.stage[i + 1][rem])
    idx = dst
  end
end
SegTree.setValue = function(self, idx, value, silent)
  self.stage[self.stagenum][idx] = value
  if not silent then
    self:update(idx)
  end
end
SegTree.new = function(n, func, emptyvalue)
  local obj = {}
  setmetatable(obj, {__index = SegTree})
  obj:create(n, func, emptyvalue)
  return obj
end

local function SA_IS(data, data_size, word_size)
  local suffix_array = {}
  local type_tag = {} -- -2: L, -1: S, 1~: i-th LMS
  for i = 1, data_size do
    suffix_array[i] = -1
    type_tag[i] = -2
  end
  local word_count = {}
  local word_count_sum = {}
  local word_pushback_count = {}
  local word_pushfront_count = {}
  for i = 1, word_size do
    word_count[i] = 0
    word_count_sum[i] = 0
    word_pushback_count[i] = 0
    word_pushfront_count[i] = 0
  end
  local lms_count = 0
  local lms_data_indexes = {}
  local sorted_lms_data_indexes = {}
  local lms_compressed_data = {}

  for i = 1, data_size do
    word_count[data[i]] = word_count[data[i]] + 1
  end
  word_count_sum[1] = word_count[1]
  for i = 2, word_size do
    word_count_sum[i] = word_count_sum[i - 1] + word_count[i]
  end
  local prev_type = -2
  for i = data_size - 1, 1, -1 do
    if data[i] == data[i + 1] then
      type_tag[i] = prev_type
    else
      type_tag[i] = data[i] < data[i + 1] and -1 or -2
      prev_type = type_tag[i]
    end
  end
  for i = 2, data_size do
    if type_tag[i - 1] == -2 and type_tag[i] == -1 then
      lms_count = lms_count + 1
      type_tag[i] = lms_count
      lms_data_indexes[lms_count] = i
      sorted_lms_data_indexes[lms_count] = -1
      lms_compressed_data[lms_count] = -1
    end
  end
  -- put LMS
  for i = 1, lms_count do
    local idx = lms_data_indexes[i]
    local w = data[idx]
    suffix_array[word_count_sum[w] - word_pushback_count[w]] = idx
    word_pushback_count[w] = word_pushback_count[w] + 1
  end
  -- put L
  do
    local w = data[data_size]
    local offset = w == 1 and 0 or word_count_sum[w - 1]
    suffix_array[offset + 1] = data_size
    word_pushfront_count[w] = word_pushfront_count[w] + 1
  end
  for sufa_idx = 1, data_size - 1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if type_tag[data_idx] == -2 then
        local w = data[data_idx]
        local offset = w == 1 and 0 or word_count_sum[w - 1]
        word_pushfront_count[w] = word_pushfront_count[w] + 1
        suffix_array[offset + word_pushfront_count[w]] = data_idx
      end
    end
  end
  -- remove LMS
  for w = 1, word_size do
    word_pushback_count[w] = 0
  end
  -- put S
  for sufa_idx = data_size, 1, -1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if -1 <= type_tag[data_idx] then
        local w = data[data_idx]
        suffix_array[word_count_sum[w] - word_pushback_count[w]] = data_idx
        word_pushback_count[w] = word_pushback_count[w] + 1
      end
    end
  end
  local lms_data_value = 0
  local prev_lms_index = 0
  local prev_lms_data_index = 0
  for sufa_idx = 1, data_size do
    local data_idx = suffix_array[sufa_idx]
    local lms_idx = type_tag[data_idx]
    if 1 <= lms_idx then
      local is_same = false
      if 0 < prev_lms_data_index and prev_lms_index ~= lms_count and lms_idx ~= lms_count then
        local len1 = lms_data_indexes[lms_idx + 1] - data_idx
        local len2 = lms_data_indexes[prev_lms_index + 1] - prev_lms_data_index
        if len1 == len2 then
          is_same = true
          for i = 0, len1 do
            if data[i + data_idx] ~= data[i + prev_lms_data_index] then
              is_same = false
              break
            end
          end
        end
      end
      if not is_same then
        lms_data_value = lms_data_value + 1
      end
      lms_compressed_data[lms_idx] = lms_data_value
      prev_lms_index = lms_idx
      prev_lms_data_index = data_idx
    end
  end
  if lms_data_value == lms_count then
    for i = 1, lms_count do
      sorted_lms_data_indexes[lms_compressed_data[i]] = lms_data_indexes[i]
    end
  else
    local lms_sa = SA_IS(lms_compressed_data, lms_count, lms_data_value)
    for i = 1, lms_count do
      sorted_lms_data_indexes[i] = lms_data_indexes[lms_sa[i]]
    end
  end
  for i = 1, lms_count do
    local inv = lms_count + 1 - i
    if inv <= i then break end
    sorted_lms_data_indexes[i], sorted_lms_data_indexes[inv]
      = sorted_lms_data_indexes[inv], sorted_lms_data_indexes[i]
  end
  -- Second Induced Sort
  for i = 1, data_size do
    suffix_array[i] = -1
  end
  for i = 1, word_size do
    word_pushback_count[i] = 0
    word_pushfront_count[i] = 0
  end
  -- put LMS
  for i = 1, lms_count do
    local idx = sorted_lms_data_indexes[i]
    local w = data[idx]
    suffix_array[word_count_sum[w] - word_pushback_count[w]] = idx
    word_pushback_count[w] = word_pushback_count[w] + 1
  end
  -- put L
  do
    local w = data[data_size]
    local offset = w == 1 and 0 or word_count_sum[w - 1]
    suffix_array[offset + 1] = data_size
    word_pushfront_count[w] = word_pushfront_count[w] + 1
  end
  for sufa_idx = 1, data_size - 1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if type_tag[data_idx] == -2 then
        local w = data[data_idx]
        local offset = w == 1 and 0 or word_count_sum[w - 1]
        word_pushfront_count[w] = word_pushfront_count[w] + 1
        suffix_array[offset + word_pushfront_count[w]] = data_idx
      end
    end
  end
  -- remove LMS
  for w = 1, word_size do
    word_pushback_count[w] = 0
  end
  -- put S
  for sufa_idx = data_size, 1, -1 do
    local data_idx = suffix_array[sufa_idx]
    if 1 < data_idx then
      data_idx = data_idx - 1
      if -1 <= type_tag[data_idx] then
        local w = data[data_idx]
        suffix_array[word_count_sum[w] - word_pushback_count[w]] = data_idx
        word_pushback_count[w] = word_pushback_count[w] + 1
      end
    end
  end
  return suffix_array
end

local SAIS = {}
SAIS.create = function(self, data, data_size, word_size)
  local sufa = SA_IS(data, data_size, word_size)
  local sufa_inv = {}
  for i = 1, data_size do sufa_inv[i] = 0 end
  for i = 1, data_size do
    sufa_inv[sufa[i]] = i
  end
  self.sufa = sufa
  self.sufa_inv = sufa_inv
  -- LCPA
  local n = data_size
  local lcpa = {}
  for i = 1, n - 1 do lcpa[i] = 0 end
  local spos = 0
  for i = 1, n do
    local lcppos = sufa_inv[i]
    if lcppos < n then
      local len = spos
      local p1, p2 = sufa[lcppos], sufa[lcppos + 1]
      p1, p2 = p1 + spos, p2 + spos
      while p1 <= n and p2 <= n do
        if data[p1] == data[p2] then
          len = len + 1
          p1, p2 = p1 + 1, p2 + 1
        else break
        end
      end
      lcpa[lcppos] = len
      spos = 1 < len and len - 1 or 0
    end
  end
  self.lcpa = lcpa
end

local s = io.read()
local t = {}
local n = #s
for i = 1, n do
  t[i] = s:byte(i) - 95
end
t[n + 1] = 1
for i = 1, n do
  t[n + 1 + i] = t[n + 1 - i]
end

local sais = SAIS
sais:create(t, 2 * n + 1, 27)
local sa = sais.sufa
local sa_inv = sais.sufa_inv
local lcpa = sais.lcpa
local st = SegTree.new(2 * n, mmi, n)
for i = 1, 2 * n do
  st:setValue(i, lcpa[i])
end
st:updateAll()

local oddlen = {}
for i = 1, n do
  local p1 = sa_inv[i]
  local p2 = sa_inv[2 * n + 2 - i]
  if p2 < p1 then p1, p2 = p2, p1 end
  oddlen[i] = st:getRange(p1, p2 - 1)
end
local evlen = {}
for i = 1, n - 1 do
  local p1 = sa_inv[i + 1]
  local p2 = sa_inv[2 * n + 2 - i]
  if p2 < p1 then p1, p2 = p2, p1 end
  evlen[i] = st:getRange(p1, p2 - 1)
end

local p3cand = {}
for p3len = 1, n do
  local hlen = mce(p3len / 2)
  if p3len % 2 == 1 then
    local center = n + 1 - hlen
    if hlen <= oddlen[center] then
      p3cand[p3len] = 1
    else
      p3cand[p3len] = 0
    end
  else
    local left = n - hlen
    if hlen <= evlen[left] then
      p3cand[p3len] = 1
    else
      p3cand[p3len] = 0
    end
  end
end
for i = 2, n do
  p3cand[i] = p3cand[i] + p3cand[i - 1]
end

local ret = 0
for p1len = 1, n - 3 do
  local hlen_p1 = mce(p1len / 2)
  local p1center = hlen_p1
  local f = false
  if p1len % 2 == 1 then
    f = hlen_p1 <= oddlen[p1center]
  else
    f = hlen_p1 <= evlen[p1center]
  end
  if f then
    local rem1 = n - p1len
    for p2len = 1, rem1 - 2 do
      local hlen_p2 = mce(p2len / 2)
      local p2center = p1len + hlen_p2
      if p2len % 2 == 1 then
        f = hlen_p2 <= oddlen[p2center]
      else
        f = hlen_p2 <= evlen[p2center]
      end
      if f then
        local rem2 = rem1 - p2len
        ret = ret + p3cand[rem2 - 1]
      end
    end
  end
end
print(ret)

yukicoder

結果

テストケース

ソースコード