BOJ 5485 평균값 수열

문제 링크입니다.

능동적 결정

$s_i$의 값이 주어지면 $m_i$의 값에 따라 $s_{i+1}$의 값 역시 결정됩니다. 이는 연쇄적으로 작용하여, 우리가 하나의 $s$ 값만 결정해 줘도 나머지 $s$ 값들이 모두 결정됩니다.

그러니 모든 조건을 만족했을 때 어떤 $s_i$가 가질 수 있는 값의 범위를 구해 주면 답을 얻을 수 있습니다. $s_1$이나 $s_{n+1}$의 범위는 한쪽이 뚫려 있어서 사실상 $s_2$와 $s_n$의 범위와 같기 때문에, 우리는 그냥 $s_2$에서 시작해 $s_n$까지 보면서 이전까지의 수들에 대해 모든 조건을 만족시킬 수 있는 $s_i$의 값의 범위들을 구하면 됩니다.

범위 구하기

$s$가 감소하지 않기 때문에, 수열의 각 원소의 값은 그 양옆의 $m$ 사이에 있어야 합니다. 즉, $s_1, s_2$만 있는 상황에서 $s_2$의 범위는 $m_1$ 이상 $m_2$ 이하입니다. 또 $s_1+s_2 = 2m_1$을 만족시키는 $s_1 \le s_2$가 항상 존재해야 합니다.

$s_{i-1}$의 범위가 $[lo, hi]$로 결정되었다고 합시다. 이때 $s_i$의 최솟값은 $[lo, hi]$가 제대로 구해졌다면 $2m_{i-1} - hi$ 입니다. $hi$가 $m_{i-1}$ 이하이므로 그냥 이렇게 식을 세워주면 됩니다.

이게 성립하려면 최댓값을 똑바로 구해줘야 합니다. $m_i$ 조건을 무시했을 때의 최댓값은 최솟값과 마찬가지로 $2m_{i-1}-lo$로 구할 수 있지만, $s_i$가 $m_i$ 이하여야 하므로 둘 중 최솟값을 다음 최댓값으로 결정하면 됩니다.

이렇게 범위를 구하다 보면 최솟값과 최댓값이 역전되는 경우가 생길 수 있습니다. 그런 경우에는 가능한 케이스가 없는 것이므로 0을 출력하면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int m[5050505];
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n; cin >> n; for(int i = 1; i <= n; i++) cin >> m[i];
	int lo = m[1], hi = m[2];
	for(int i = 3; i <= n; i++){
		int t = lo;
		lo = 2*m[i-1]-hi;
		hi = min(2*m[i-1]-t, m[i]);
	}
	cout << max(0, hi-lo+1);
}