結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー Kohei
提出日時 2026-07-26 17:47:42
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 498 ms / 2,000 ms
+ 849µs
コード長 1,905 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 238 ms
コンパイル使用メモリ 95,856 KB
実行使用メモリ 316,856 KB
最終ジャッジ日時 2026-07-26 17:48:13
合計ジャッジ時間 29,528 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from typing import List, Any
N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N - 1):
    B.append(A[i + 1] - A[i])

def count_palindromic_sublists(seq: List[Any]) -> int:
    """
    Manacherのアルゴリズムを利用して、リスト seq に含まれる
    回文部分リストの総数を O(N) で計算する関数。
    """
    if not seq:
        return 0

    # リストの要素と絶対に被らないダミーオブジェクトを生成
    # （これらはメモリ上のアドレスで比較されるため、元の seq に何が入っていても安全です）
    START = object()
    END = object()
    DUMMY = object()

    # ダミー要素を挟み込んだ新しいリスト t を構築
    # 例: [-2, 1, -2] -> [START, DUMMY, -2, DUMMY, 1, DUMMY, -2, DUMMY, END]
    t = [START]
    for item in seq:
        t.append(DUMMY)
        t.append(item)
    t.append(DUMMY)
    t.append(END)

    n = len(t)
    p = [0] * n

    center = 0
    right = 0

    for i in range(1, n - 1):
        i_mirror = 2 * center - i

        # i が現在の right の内側にある場合、対称位置の半径を利用して計算をスキップ
        if right > i:
            p[i] = min(right - i, p[i_mirror])
        else:
            p[i] = 0

        # 中心 i を基準に回文を左右に拡張
        # 要素同士が `==` で比較可能な任意のオブジェクトに対して機能します
        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1

        # 必要に応じて center と right を更新
        if i + p[i] > right:
            center = i
            right = i + p[i]

    # 各中心について、生成できる回文の数は (半径 + 1) // 2 個となる
    total_palindromes = sum((radius + 1) // 2 for radius in p)

    return total_palindromes

ans = count_palindromic_sublists(B)
ans += N
print(ans)
0