結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー titia
提出日時 2025-12-18 01:27:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 605 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 469 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 282,612 KB
最終ジャッジ日時 2025-12-18 01:27:44
合計ジャッジ時間 22,793 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

if N==1:
    print(1)
    exit()

X=[]
for i in range(1,N):
    X.append(A[i]-A[i-1])
    X.append(-1)

X.pop()
S=X

LEN=len(S)
i=0
j=0
R=[0]*LEN # 文字 i を中心とする最長の回文の半径

while i<LEN:
    while i-j>=0 and i+j<LEN and S[i-j]==S[i+j]:
        j+=1
    R[i]=j
    
    k=1
    while i-k>=0 and i+k<LEN and k+R[i-k]<j:
        R[i+k]=R[i-k]
        k+=1

    i+=k
    j-=k

ANS=0
for i in range(len(X)):
    if i%2==1:
        ANS+=R[i]//2+1
    else:
        ANS+=(R[i]+1)//2

print(ANS+2)
0