結果

問題 No.765 ukuku 2
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:27:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,409 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 83,360 KB
最終ジャッジ日時 2025-04-24 12:29:43
合計ジャッジ時間 4,659 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n == 0:
        print(0)
        return

    # Manacher's algorithm to find the longest palindromic substring
    # Convert S to handle even and odd lengths uniformly
    T = '#'.join('^{}$'.format(S))
    c = 0
    r = 0
    P = [0] * len(T)
    max_len = 0
    max_centers = []

    for i in range(1, len(T)-1):
        mirror = 2*c - i
        if i < r:
            P[i] = min(r - i, P[mirror])
        # Expand around center i
        a, b = i + P[i] + 1, i - P[i] - 1
        while T[a] == T[b]:
            P[i] += 1
            a += 1
            b -= 1
        # Update the center and right bound if needed
        if i + P[i] > r:
            c = i
            r = i + P[i]
        # Update the maximum length
        current_len = P[i]
        if current_len > max_len:
            max_len = current_len
            max_centers = [i]
        elif current_len == max_len:
            max_centers.append(i)

    original_max = max_len

    # Now, find all intervals of palindromes with length original_max
    # original_max is the length in the transformed string T
    # The actual length in S is original_max for odd (since transformed length is 2*radius +1)
    # and original_max for even (transformed length is 2*radius)
    # Wait, no. In Manacher's algorithm, the actual length of the palindrome in S is P[i]
    # For example, if the palindrome in T has length P[i], then the actual length is P[i]
    # Because T is constructed with # between each character. So for example, a palindrome in T of length 5 (like #a#b#a#) corresponds to "aba" in S, which has length 3.
    # So the actual length in S is (P[i] + 1) // 2 if the center is on a character (odd length), and P[i] // 2 if the center is on a '#' (even length).
    # Wait, the actual length in S is P[i]. Because the transformed string T has each character of S separated by '#', so the actual length of the palindrome in S is P[i]. For example:
    # S = "aba", T becomes "^#a#b#a#$"
    # The palindrome around 'b' (index 3 in T) has P[i] = 3, which corresponds to "aba" in S, length 3.
    # Another example: S = "abba", T becomes "^#a#b#b#a#$"
    # The palindrome around the middle '#' (index 4) has P[i] = 4, which corresponds to "abba" in S, length 4.
    # So the actual length in S is P[i].

    # So original_max is the length of the longest palindrome in S.

    # Now, find all intervals in S that are part of a palindrome of length original_max.

    # To find the intervals in S, for each center in max_centers:
    # For a center i in T, the palindrome in T is from i - P[i] to i + P[i]
    # The corresponding palindrome in S starts at (i - P[i]) // 2 and ends at (i + P[i] - 1) // 2 - 1 (since each character in S is represented by a position in T with even index)
    # Or wait, let's think:
    # The transformed string T has length 2n + 3 (including ^ and $)
    # The original S has indices 0..n-1.
    # For a palindrome in T centered at i with radius P[i], the corresponding start and end in S are:
    # start = (i - P[i]) // 2
    # end = (i + P[i] - 1) // 2 - 1
    # Wait, perhaps a better way is to calculate the start and end in S.
    # For example, in T, each character in S is at even indices (starting from 1). The # are at odd indices.
    # So for a palindrome in T spanning from a to b, the corresponding positions in S are (a//2 - 1) to (b//2 - 1)
    # For example, in T, the substring from 1 to 3 (indices) is "#a#", which corresponds to S[0:0] = 'a'.
    # So for a palindrome in T centered at i with radius P[i], the start and end in S are:
    start = (i - P[i] + 1) // 2
    end = (i + P[i] - 1) // 2 - 1
    # Wait, maybe not. Let's take an example:
    # S = "abba", T is "^#a#b#b#a#$"
    # The center is at index 4 (the middle '#') with P[i] = 4.
    # The palindrome in T spans from 0 to 8 (indices), which is "^#a#b#b#a#$" from 0 to 8 (but T has length 11).
    # The corresponding palindrome in S is "abba", which is indices 0 to 3.
    # So for i=4, P[i]=4. The start in S is (4 -4 +1)//2 = (1)//2 = 0. The end is (4 +4 -1)//2 -1 = (7)//2 -1 = 3-1=2. But "abba" is from 0 to 3. So this calculation is incorrect.

    # Alternative approach: The start in S is (i - P[i]) // 2
    # The end in S is (i + P[i]) // 2 - 1
    # For example, i=4, P[i]=4:
    # start = (4-4)//2 = 0
    # end = (4+4)//2 -1 = 4 -1 =3. So the interval is [0,3], which is correct.

    # Another example: i=3 in T for S="aba":
    # T is "^#a#b#a#$", i=3 (the 'b'), P[i]=3.
    # start = (3-3)//2 =0
    # end = (3+3)//2 -1 =3-1=2. So interval [0,2], which is correct.

    # So the formula is:
    # start = (i - P[i]) // 2
    # end = (i + P[i]) // 2 -1

    # So for each center in max_centers, compute start and end in S.

    delta = [0]*(n+1)
    for i in max_centers:
        start = (i - original_max) // 2
        end = (i + original_max) // 2 -1
        if start <0 or end >=n:
            continue
        delta[start] +=1
        delta[end+1] -=1

    # Compute prefix sum
    covered = [False]*n
    current =0
    for i in range(n):
        current += delta[i]
        if current >0:
            covered[i] = True

    # Check if all are covered
    all_covered = all(covered)
    if not all_covered:
        print(original_max)
    else:
        print(original_max -1)

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