結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 14:47:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 133,500 KB
最終ジャッジ日時 2025-06-12 14:49:35
合計ジャッジ時間 4,857 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]
        ptr += 1
        strings.append(s)

    # Precompute hashes for each string
    base1 = 911382629
    mod1 = 10**18 + 3
    base2 = 3571428571
    mod2 = 10**18 + 7

    hash1 = []
    hash2 = []
    for s in strings:
        h1 = [0]
        current1 = 0
        h2 = [0]
        current2 = 0
        for c in s:
            current1 = (current1 * base1 + ord(c)) % mod1
            h1.append(current1)
            current2 = (current2 * base2 + ord(c)) % mod2
            h2.append(current2)
        hash1.append(h1)
        hash2.append(h2)

    len_list = [len(s) for s in strings]

    M = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr +=3

    sum_lcp = 0
    n = N
    max_x_mod = n * (n-1)

    for _ in range(M):
        # Compute i and j
        if (n-1) == 0:
            i = 1
            j = 1
        else:
            i = (x // (n-1)) + 1
            j = (x % (n-1)) + 1

        if i > j:
            i, j = j, i
        else:
            j += 1

        # Ensure i < j and j <= n
        if j > n:
            j = n

        i_idx = i - 1
        j_idx = j - 1

        s_i = strings[i_idx]
        s_j = strings[j_idx]
        len_i = len_list[i_idx]
        len_j = len_list[j_idx]
        min_len = min(len_i, len_j)

        low = 0
        high = min_len
        ans = 0

        while low <= high:
            mid = (low + high) // 2
            h1_i = hash1[i_idx][mid]
            h1_j = hash1[j_idx][mid]
            h2_i = hash2[i_idx][mid]
            h2_j = hash2[j_idx][mid]

            if h1_i == h1_j and h2_i == h2_j:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        sum_lcp += ans

        x = (x + d) % max_x_mod

    print(sum_lcp)

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