結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 14:43:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,921 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 139,112 KB
最終ジャッジ日時 2025-06-12 14:43:06
合計ジャッジ時間 5,317 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    strings = []
    for _ in range(N):
        s = input[ptr].strip()
        strings.append(s)
        ptr += 1
    
    # Precompute rolling hashes for each string
    base1 = 911382629
    mod1 = 10**18 + 3
    base2 = 3571428571
    mod2 = 10**18 + 7
    
    pre_h1 = []
    pre_h2 = []
    for s in strings:
        m = len(s)
        h1 = [0] * (m + 1)
        h2 = [0] * (m + 1)
        for i in range(1, m + 1):
            h1[i] = (h1[i-1] * base1 + ord(s[i-1])) % mod1
            h2[i] = (h2[i-1] * base2 + ord(s[i-1])) % mod2
        pre_h1.append(h1)
        pre_h2.append(h2)
    
    M = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr += 3
    
    N2 = N * (N - 1)
    
    sum_lcp = 0
    
    for _ in range(M):
        current_x = x
        n_minus_1 = N - 1
        i = (current_x // n_minus_1) + 1
        j = (current_x % n_minus_1) + 1
        
        if i > j:
            i, j = j, i
        else:
            j += 1
        
        a = i - 1
        b = j - 1
        
        len_a = len(strings[a])
        len_b = len(strings[b])
        L = min(len_a, len_b)
        
        low = 0
        high = L
        best = 0
        
        while low <= high:
            mid = (low + high) // 2
            if mid > len_a or mid > len_b:
                high = mid - 1
                continue
            
            h1_a = pre_h1[a][mid]
            h1_b = pre_h1[b][mid]
            h2_a = pre_h2[a][mid]
            h2_b = pre_h2[b][mid]
            
            if h1_a == h1_b and h2_a == h2_b:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        
        sum_lcp += best
        
        x = (current_x + d) % N2
    
    print(sum_lcp)

if __name__ == "__main__":
    main()
0