結果

問題 No.515 典型LCP
ユーザー 👑 maspymaspy
提出日時 2020-07-01 02:00:20
言語 PyPy3
(7.0.0)
結果
AC  
実行時間 936 ms / 1,000 ms
コード長 1,193 Byte
コンパイル時間 1,809 ms
使用メモリ 108,176 KB
最終ジャッジ日時 2020-07-01 02:00:45

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 936 ms
107,772 KB
testcase_01 AC 815 ms
108,176 KB
testcase_02 AC 412 ms
74,764 KB
testcase_03 AC 102 ms
67,756 KB
testcase_04 AC 102 ms
67,340 KB
testcase_05 AC 316 ms
75,288 KB
testcase_06 AC 330 ms
73,820 KB
testcase_07 AC 321 ms
74,500 KB
testcase_08 AC 391 ms
73,580 KB
testcase_09 AC 348 ms
75,556 KB
testcase_10 AC 341 ms
75,292 KB
testcase_11 AC 331 ms
74,764 KB
testcase_12 AC 350 ms
74,764 KB
testcase_13 AC 327 ms
73,584 KB
testcase_14 AC 153 ms
74,312 KB
testcase_15 AC 299 ms
73,680 KB
testcase_16 AC 311 ms
74,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
S = read().split()
M, X, D = map(int, S[-3:])
inds, words = zip(*sorted(enumerate(S[:-3], 1), key=itemgetter(1)))

re_index = [0] * (N+1)
for i,x in enumerate(inds):
    re_index[x] = i

def LCP_naive(S, T):
    n = 0
    for s,t in zip(S,T):
        if s != t:
            break
        n += 1
    return n

A = [LCP_naive(S, T) for S, T in zip(words, words[1:])]

N = len(A)

sp = [0] * (20 * N)
for n in range(N):
    sp[n] = A[n]
for i in range(1, 20):
    dx = 1 << i
    if N < dx:
        break
    for n in range(i*N, i*N+N + 1- dx):
        sp[n] = min(sp[n-N], sp[n-N+dx//2])

def lcp(i,j):
    i = re_index[i]
    j = re_index[j]
    if i > j:
        i,j = j,i
    items = j - i
    if items == 1:
        return A[i]
    k = (items - 1).bit_length() - 1
    dx = 1 << k
    return min(sp[k*N+i], sp[k*N+j-dx])

answer = 0
MOD = N * (N+1)
for _ in range(M):
    i = X // N + 1
    j = X % N + 1
    if i > j:
        i,j = j,i
    else:
        j += 1
    answer += lcp(i,j)
    X = (X + D) % MOD

print(answer)
0