結果

問題 No.958 たぷりすたべる (回文)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:00:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,058 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 130,724 KB
最終ジャッジ日時 2025-04-16 00:02:24
合計ジャッジ時間 6,721 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    S = data[idx]
    idx += 1
    queries = [int(data[idx + i]) for i in range(Q)]
    
    # Check if S is a palindrome
    is_palindrome = True
    for i in range(N // 2):
        if S[i] != S[N - 1 - i]:
            is_palindrome = False
            break
    
    if is_palindrome:
        for A in queries:
            max_r = min(A - 1, K * N - A)
            print(2 * max_r + 1)
        return
    
    # Else, compute using Manacher's on S + S
    T = S + S
    n = len(T)
    max_radius = [0] * n
    
    # Manacher's algorithm
    C, R = 0, 0
    L = 0
    max_len = 0
    P = [0] * (2 * n + 1)
    T_m = '#' + '#'.join(T) + '#'
    center, right = 0, 0
    P = [0] * len(T_m)
    
    for i in range(len(T_m)):
        mirror = 2 * center - i
        if i < right:
            P[i] = min(right - i, P[mirror])
        a, b = i + P[i] + 1, i - P[i] - 1
        while a < len(T_m) and b >= 0 and T_m[a] == T_m[b]:
            P[i] += 1
            a += 1
            b -= 1
        if i + P[i] > right:
            center, right = i, i + P[i]
    
    # Convert to radii in original T (without #)
    max_radius = [0] * n
    for i in range(1, len(T_m) - 1):
        original_pos = (i - 1) // 2
        if original_pos >= n:
            continue
        length = P[i]
        max_radius[original_pos] = max(max_radius[original_pos], length // 2)
    
    # Precompute r_infinite for each position in original S (0-based)
    r_infinite = [0] * N
    for p in range(N):
        r_infinite[p] = max_radius[p]
        if p + N < len(max_radius):
            r_infinite[p] = max(r_infinite[p], max_radius[p + N])
    
    for A in queries:
        pos_in_T = (A - 1) % N
        r = r_infinite[pos_in_T]
        r_boundary = min(A - 1, K * N - A)
        ans_r = min(r, r_boundary)
        print(2 * ans_r + 1)

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