#1157003 (C++23) No.3392 Count 23578 Sequence

• 問題: No.3392 Count 23578 Sequence
• ユーザー: kwm_t
• 提出日時: 2026-04-10 21:00:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 116 ms / 2,000 ms
• コード長: 3,965 bytes
• コンパイル時間: 2,308 ms
• コンパイル使用メモリ: 337,672 KB
• 実行使用メモリ: 26,848 KB
• 最終ジャッジ日時: 2026-04-10 21:01:18
• 合計ジャッジ時間: 21,051 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 48

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_STRING_MANACHER_HPP
#define KWM_T_STRING_MANACHER_HPP

#include <vector>
#include <algorithm>

/**
 * @brief Manacher法（回文半径）
 *
 * 各中心 i に対して、最大の回文半径を求める（奇数長）
 *
 * 計算量:
 *   O(N)
 *
 * @tparam T 比較可能な型
 *
 * @param s 入力列
 * @return radius[i]: 中心iの回文半径
 *
 * verified
 *  https://atcoder.jp/contests/abc349/submissions/74809646
 *  https://mojacoder.app/users/dyktr_06/contests/mma-014/submissions/bc2fce82-fe18-4124-86e9-336f0b308c99
 */
namespace kwm_t::string {

// =========================
// core: 奇数長
// =========================
template <typename T>
std::vector<int> manacher(const std::vector<T>& s) {
	int n = (int)s.size();
	std::vector<int> radius(n);

	int i = 0, j = 0;
	while (i < n) {
		while (i - j >= 0 && i + j < n && s[i - j] == s[i + j]) ++j;
		radius[i] = j;

		int k = 1;
		while (i - k >= 0 && i + k < n && k + radius[i - k] < j) {
			radius[i + k] = radius[i - k];
			++k;
		}

		i += k;
		j -= k;
	}
	return radius;
}

// =========================
// wrapper: 偶数対応
// =========================
template <typename T>
std::vector<int> manacher_all(const std::vector<T>& s, const T& dummy) {
	if (s.empty()) return {};

	std::vector<T> w(2 * (int)s.size() - 1, dummy);
	for (int i = 0; i < (int)s.size(); ++i) w[2 * i] = s[i];

	auto r = manacher(w);

	return r; // 「挿入後配列上の半径」を返す（raw）
}

// =========================
// utility: 開始位置ごとの最大回文長
// =========================
inline std::vector<int> longest_palindrome_from_each(const std::string& s) {
	if (s.empty()) return {};

	// 文字列展開
	std::string t;
	t.reserve(2 * s.size() - 1);
	for (int i = 0; i < (int)s.size(); ++i) {
		if (i) t += '*';
		t += s[i];
	}

	// Manacher
	std::vector<int> r(t.size());
	{
		int i = 0, j = 0;
		while (i < (int)t.size()) {
			while (i - j >= 0 && i + j < (int)t.size() && t[i - j] == t[i + j]) ++j;
			r[i] = j;

			int k = 1;
			while (i - k >= 0 && i + k < (int)t.size() && k + r[i - k] < j) {
				r[i + k] = r[i - k];
				++k;
			}

			i += k;
			j -= k;
		}
	}

	std::vector<int> res(s.size());

	for (int i = 0; i < (int)r.size(); ++i) {
		int len, l;

		if (i % 2 == 0) {
			int k = (r[i] + 1) / 2;
			l = i / 2 + 1 - k;
			len = 2 * k - 1;
		}
		else {
			int k = r[i] / 2;
			l = (i + 1) / 2 - k;
			len = 2 * k;
		}

		if (0 <= l && l < (int)res.size())
			res[l] = std::max(res[l], len);
	}

	// 伝播
	for (int i = 1; i < (int)res.size(); ++i) {
		res[i] = std::max(res[i], res[i - 1] - 2);
	}

	return res;
}

} // namespace kwm_t::string

#endif // KWM_T_STRING_MANACHER_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n; cin >> n;
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	vector<int>a(n), b(n - 1);
	rep(i, n)cin >> a[i];
	rep(i, n - 1)b[i] = a[i + 1] - a[i];
	long long ans = n;
	auto mn = kwm_t::string::manacher_all(b, INF);
	for (int i = 0; i < (int)mn.size(); ++i) {
		if (i % 2 == 0) ans += (mn[i] + 1) / 2;
		else ans += (mn[i] + 0) / 2;
	}
	cout << ans << endl;
	return 0;
}