백준 5485 평균값 수열

문제

https://www.acmicpc.net/problem/5485

5485번: 평균값 수열

 

풀이

편의상 평균값수열을 A라고하자. 

Si <= Si+1이다. Si + Si+1 = 2Ai이다. 따라서 Si <= Ai (Si <= 2Ai-Si) 여야한다.

S[0]값을 임의로 정하면 나머지 S의 원소들이 정해지고 Si<=A{i]인지 검사하는 것은 O(N)이 소요되고 S[0]값에 많은 수들을 넣어보기엔... 값의 범위가 너무크다.

심지어 5백만이라는 정신나간 수열의 길이는 O(N * logN)으로 이걸 체크해줘도 위험하다. (될 것 같긴한데 미리 스포를하자면 풀이는 O(N)이다.)

이럴땐 식 정리를 좀더 해봐서 효율적인 알고리즘을 찾아봐야한다.

S[0]를 정해준다면, S[1] = 2A[0] - S[0]이다. S[2] = 2A[1] - S[1] = 2A[1] - 2A{0] + S[0]이다.

그렇게 정리해나간다면 배열A와 S[0]로부터 S[i]를 계산할 수 있게된다!

S[i] = 2 * (A[i-1] + A[i-3] + ... ) - 2*(A[i-2] + A[i-4] + ... ) + (S[0] if i is even else -S[0]

여기서 배열A에 관한 식의 값은 누적합을 응용해 쉽게 구할 수 있다.

imoseven = [0] * N
imosodd = [0] * N
for i in range(N):
    if i % 2 == 0:
        imoseven[i] = 2 * A[i]
    else:
        imosodd[i] = 2 * A[i]
for i in range(1, N):
    imoseven[i] += imoseven[i - 1]
    imosodd[i] += imosodd[i - 1]

다시 정리하면

if is odd:
	S[i] = 2 * (imoseven[i-1] - imosodd[i-1]) -S[0]
else:
	S[i] = 2 * (imosodd[i-1] - imoseven[i-1]) +S[0]

이제 S[i] <= A[i]이므로 모든 부등식을 S[0]에 대해 정리할 수 있다.

여기서 또한 S[0]는 어떤 범위안의 수로 정해줘야지 만족하고 그 밖에서는 만족하지 않음이 증명됐다!

if is odd:
    S[0] >= 2 * (imoseven[i-1] - imosodd[i-1]) - A[i]
else:
    S[0] <= A[i] -  2 * (imosodd[i-1] - imoseven[i-1])

 

 

모든 부등식을 만족하기 위해선

모든 i에 대해

i가 홀수라면 2 * (imoseven[i-1] - imosodd[i-1]) - A[i]의 최대를 구하고(S[0]는 이 값보다 커야하므로)

i가 짝수라면  A[i] -  2 * (imosodd[i-1] - imoseven[i-1])의 최소를 구한다. (S[0]는 이 값보다 작아햐므로)

전자의 최대값을 X라하고 후자의 최소값을 Y라할때

S[0]는 [X,Y]안에서 만족하므로 가능한 경우의수는 Y-X+1이된다.

 

나도 궁금한 것

예외처리를위해 출력은 max(0,Y-X+1)을 해줬다.

Y < X인 경우가 있을지는 따로 증명은 안해봤으나 직관적으론 있어보인다 아마도..