結果

問題 No.515 典型LCP
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:47:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,573 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 103,388 KB
最終ジャッジ日時 2025-06-12 14:49:41
合計ジャッジ時間 13,837 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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()
        ptr += 1
        strings.append(s)

    # Preprocess hash prefix arrays
    base = 911382629
    mod = 10**18 + 3
    pre_hash = []
    for s in strings:
        m = len(s)
        h = [0] * (m + 1)
        for i in range(1, m + 1):
            h[i] = (h[i - 1] * base + ord(s[i - 1])) % mod
        pre_hash.append(h)

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

    mod_total = n * (n - 1)
    sum_lcp = 0

    for _ in range(M):
        i = (x // (n - 1)) + 1
        j = (x % (n - 1)) + 1

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

        if i >= j or i < 1 or j > n:
            s_i_hash = []
            s_j_hash = []
        else:
            s_i_hash = pre_hash[i - 1]
            s_j_hash = pre_hash[j - 1]

        len_i = len(s_i_hash) - 1
        len_j = len(s_j_hash) - 1
        max_len = min(len_i, len_j)

        low = 0
        high = max_len
        lcp = 0

        while low <= high:
            mid = (low + high) // 2
            if mid > max_len:
                high = mid - 1
                continue
            if s_i_hash[mid] == s_j_hash[mid]:
                lcp = mid
                low = mid + 1
            else:
                high = mid - 1

        sum_lcp += lcp

        x = (x + d) % mod_total

    print(sum_lcp)

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