結果

問題 No.515 典型LCP
ユーザー maspymaspy
提出日時 2020-07-01 02:00:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 699 ms / 1,000 ms
コード長 1,193 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 118,772 KB
最終ジャッジ日時 2024-09-13 15:46:26
合計ジャッジ時間 6,806 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 699 ms
118,772 KB
testcase_01 AC 600 ms
118,764 KB
testcase_02 AC 315 ms
79,564 KB
testcase_03 AC 39 ms
52,828 KB
testcase_04 AC 38 ms
52,936 KB
testcase_05 AC 231 ms
79,140 KB
testcase_06 AC 265 ms
79,368 KB
testcase_07 AC 234 ms
79,328 KB
testcase_08 AC 298 ms
79,348 KB
testcase_09 AC 231 ms
77,116 KB
testcase_10 AC 254 ms
80,088 KB
testcase_11 AC 241 ms
80,348 KB
testcase_12 AC 239 ms
80,124 KB
testcase_13 AC 247 ms
75,872 KB
testcase_14 AC 76 ms
74,176 KB
testcase_15 AC 223 ms
79,428 KB
testcase_16 AC 222 ms
77,232 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