結果

問題 No.958 たぷりすたべる (回文)
ユーザー gew1fw
提出日時 2025-06-12 21:25:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,132 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 119,168 KB
最終ジャッジ日時 2025-06-12 21:26:52
合計ジャッジ時間 8,373 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manachers(s):
    # Transform the string to include special characters
    transformed = '#' + '#'.join(s) + '#'
    n = len(transformed)
    P = [0] * n
    C = R = 0

    for i in range(n):
        # Find the mirror position
        mirror = 2 * C - i
        if i < R:
            # Initialize P[i] to the minimum of the remaining palindrome length or the mirror's length
            P[i] = min(R - i, P[mirror])

        # Expand around the center
        a, b = i + (1 + P[i]), i - (1 + P[i])
        while a < n and b >= 0 and transformed[a] == transformed[b]:
            P[i] += 1
            a += 1
            b -= 1

        # Update the center and right boundary if a longer palindrome is found
        if i + P[i] > R:
            C = i
            R = i + P[i]

    return P

def is_palindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            return False
    return True

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1

    # Check if S is a palindrome
    s_palindrome = is_palindrome(S)
    s_len = len(S)

    # Concatenate S with itself
    s_concat = S + S
    concat_len = 2 * s_len

    # Run Manacher's algorithm on the concatenated string
    P = manachers(s_concat)
    # Precompute R for each position in the first S
    R = [0] * s_len
    for pos in range(s_len):
        expanded_pos = 2 * pos + 1
        if expanded_pos < len(P):
            R[pos] = P[expanded_pos] // 2
        else:
            R[pos] = 0  # This should not happen as the P array is computed for the entire s_concat

    # Process each query
    for _ in range(Q):
        A_i = int(input[ptr])
        ptr += 1
        x_0 = A_i - 1
        pos_in_S = x_0 % s_len
        max_r_S = R[pos_in_S]

        max_r_T = min(x_0, (K * s_len - 1) - x_0)

        if s_palindrome:
            r = max_r_T
        else:
            r = min(max_r_S, max_r_T)

        print(2 * r + 1)

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