IOI 2005-day1 Mean Sequence

問題文 : 平均数列

解法 :
数列の初項を決めると, 残りの数列の値も一意に定まる.
更に, 初項k の平均数列が作れなければ, 初項をk + 1 とする平均数列(またはk - 1 とする平均数列, あるいは両方) が作れないことが分かる. ゆえに, この数列の初項の値は連続していることが分かる.
そこで, 初項の値としてありうる範囲を計算すると, 2 * m1 - m2 ≦ x ≦ m1 となることが分かる. この値を遷移させて行き, 最終項としてありうる数の上限と下限を定める.
値の遷移はO(1) で行えるため, 計算量はO(n) となる.

コード :

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;
typedef long long int lint;

lint t;

int main()
{
	int n;
	
	scanf("%d", &n);
	
	lint upper, lower;
	lint nextu = LLONG_MAX, nextl = LLONG_MIN;
	lint prev = -1;
	for (int i = 0; i < n; i++){
		scanf("%lld", &t);
		if (~prev){
			upper = min(nextu, max(prev, 2 * prev - t));
			lower = max(nextl, min(prev, 2 * prev - t));
			nextu = 2 * prev - lower;
			nextl = 2 * prev - upper;
			//printf("upper = %lld lower = %lld nextu = %lld nextl = %lld\n", upper, lower, nextu, nextl);
		}
		prev = t;
	}
	//printf("upper = %lld, lower = %lld\n", upper, lower);
	printf("%lld\n", max(0ll, upper - lower + 1));
	
	return (0);
}