끝까지 남는 수 2

정답은 $\min(A_1,\ldots,A_N)+N-1$이다.

어떤 연산 직전의 최솟값을 $m$, 제거하는 값을 $x$라 하자. 남아 있는 값 $y$는 다음 두 경우 중 하나이다.

• $y\le x$이면 $y+1$이 되므로 $m+1$ 이상이다.
• $y>x$이면 값이 그대로이다. 와 는 정수이고 이므로 이다.

따라서 최솟값은 매 연산마다 적어도 1 증가한다. 연산은 정확히 $N-1$번 수행하므로 마지막 값은 최초 최솟값에 $N-1$을 더한 값 이상이다.

이제 매번 현재 최댓값을 하나 제거하자. 남은 모든 값이 제거한 값 이하이므로 모두 1 증가한다. 최솟값이었던 정수가 모두 사라지는 일은 없다. 모든 값이 같아서 최솟값 하나를 제거하더라도 다른 최솟값이 남는다. 따라서 매 연산에서 최솟값은 정확히 1 증가하여 앞의 하한을 달성한다.

$N=1$이면 연산을 하지 않으며 같은 공식이 그대로 성립한다. 단일 서브태스크의 의도된 풀이는 입력을 읽으면서 최솟값만 저장하는 것이다. 시간 복잡도는 $O(N)$, 추가 공간 복잡도는 $O(1)$이다.

나이브 풀이는 매번 최댓값을 찾아 제거하고 남은 모든 값을 직접 갱신한다. 올바른 결과를 얻지만 시간 복잡도가 $O(N^2)$이고 공간 복잡도는 $O(N)$이므로 최대 입력에서 시간 초과가 발생한다.

어떤 정수도 최대 $N-1$번만 증가하므로, 정답과 모든 시뮬레이션 중간값은 최대 $10^9+200\,000-1=1\,000\,199\,999$이다. 모든 정수 계산은 부호 있는 64비트 범위 안에 있다.

Solution written by GPT6