結果

問題 No.515 典型LCP
ユーザー maspymaspy
提出日時 2020-05-08 20:45:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 718 ms / 1,000 ms
コード長 1,193 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 86,832 KB
実行使用メモリ 115,024 KB
最終ジャッジ日時 2023-09-16 08:34:37
合計ジャッジ時間 6,986 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 718 ms
115,024 KB
testcase_01 AC 639 ms
114,916 KB
testcase_02 AC 341 ms
79,964 KB
testcase_03 AC 75 ms
71,208 KB
testcase_04 AC 75 ms
71,168 KB
testcase_05 AC 263 ms
79,544 KB
testcase_06 AC 288 ms
80,000 KB
testcase_07 AC 266 ms
79,480 KB
testcase_08 AC 326 ms
79,564 KB
testcase_09 AC 267 ms
79,976 KB
testcase_10 AC 291 ms
80,964 KB
testcase_11 AC 270 ms
80,664 KB
testcase_12 AC 270 ms
80,724 KB
testcase_13 AC 284 ms
79,884 KB
testcase_14 AC 114 ms
79,976 KB
testcase_15 AC 250 ms
79,672 KB
testcase_16 AC 254 ms
79,888 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