結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 20:12:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,715 bytes
コンパイル時間 485 ms
コンパイル使用メモリ 81,952 KB
実行使用メモリ 122,564 KB
最終ジャッジ日時 2025-06-12 20:16:22
合計ジャッジ時間 5,136 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)

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

    n = N

    max_len = max(len(s) for s in strings)
    mod = 10**18 + 3
    base = 911382629

    powers = [1] * (max_len + 1)
    for i in range(1, max_len + 1):
        powers[i] = (powers[i-1] * base) % mod

    prefix_hashes = []
    for s in strings:
        m = len(s)
        ph = [0] * (m + 1)
        for i in range(m):
            ph[i + 1] = (ph[i] * base + ord(s[i])) % mod
        prefix_hashes.append((ph, m))

    sum_lcp = 0
    current_x = x
    n_val = n

    for _ in range(M):
        if n_val == 1:
            break  # No pairs possible

        i = (current_x // (n_val - 1)) + 1
        j = (current_x % (n_val - 1)) + 1

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

        if i >= j or j > n_val:
            current_x = (current_x + d) % (n_val * (n_val - 1))
            continue

        idx_i = i - 1
        idx_j = j - 1

        ph_i, len_i = prefix_hashes[idx_i]
        ph_j, len_j = prefix_hashes[idx_j]

        low = 0
        high = min(len_i, len_j)
        ans = 0

        while low <= high:
            mid = (low + high) // 2
            if ph_i[mid] == ph_j[mid]:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        sum_lcp += ans

        current_x = (current_x + d) % (n_val * (n_val - 1))

    print(sum_lcp)

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