結果

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

ソースコード

diff # 

MOD = 10**18 + 3
B = 911382629

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    strings = []
    for _ in range(n):
        strings.append(input[ptr])
        ptr += 1
    m = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr +=3
    
    hash_arrays = []
    lengths = []
    for s in strings:
        l = len(s)
        h = [0] * (l + 1)
        for i in range(l):
            h[i+1] = (h[i] * B + (ord(s[i]) - ord('a') + 1)) % MOD
        hash_arrays.append(h)
        lengths.append(l)
    
    total = 0
    n_val = n
    divisor = n_val - 1
    max_x = n_val * divisor
    current_x = x
    
    for _ in range(m):
        if divisor == 0:
            i = 1
            j_initial = 1
        else:
            i = (current_x // divisor) + 1
            j_initial = (current_x % divisor) + 1
        
        if i > j_initial:
            i, j = j_initial, i
        else:
            j = j_initial + 1
        
        i_idx = i - 1
        j_idx = j - 1
        
        h_i = hash_arrays[i_idx]
        len_i = lengths[i_idx]
        h_j = hash_arrays[j_idx]
        len_j = lengths[j_idx]
        
        low = 0
        high = min(len_i, len_j)
        ans = 0
        
        while low <= high:
            mid = (low + high) // 2
            if h_i[mid] == h_j[mid]:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        
        total += ans
        current_x = (current_x + d) % max_x
    
    print(total)

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