結果

問題 No.515 典型LCP
ユーザー maspymaspy
提出日時 2020-05-08 20:45:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 640 ms / 1,000 ms
コード長 1,193 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 119,072 KB
最終ジャッジ日時 2024-07-03 09:57:27
合計ジャッジ時間 6,049 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 640 ms
118,968 KB
testcase_01 AC 575 ms
119,072 KB
testcase_02 AC 307 ms
79,436 KB
testcase_03 AC 37 ms
54,208 KB
testcase_04 AC 37 ms
53,564 KB
testcase_05 AC 229 ms
79,300 KB
testcase_06 AC 262 ms
79,428 KB
testcase_07 AC 232 ms
79,296 KB
testcase_08 AC 295 ms
79,236 KB
testcase_09 AC 224 ms
77,104 KB
testcase_10 AC 247 ms
80,148 KB
testcase_11 AC 232 ms
80,200 KB
testcase_12 AC 232 ms
80,252 KB
testcase_13 AC 241 ms
76,192 KB
testcase_14 AC 75 ms
74,068 KB
testcase_15 AC 220 ms
79,304 KB
testcase_16 AC 216 ms
77,224 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