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

아이디어

이 문제에서 수열의 '순서'는 중요하지 않으므로 수열이 아닌 집합으로 생각하자.

기본적으로 $A$의 최댓값 1개만을 선택한 부분집합 $B=\left\{\max(A)\right\}$에 대해 $\mathrm{med}$ 값이 최대가 되며, 이 이상 원소를 더하는 것은 $\mathrm{med}$ 값을 늘릴 수 없다. 그러나 $B$에 $0$부터 연속하여 원소를 추가할 수 있다면, 그 길이만큼 $\mathrm{mex}$ 값이 더해져 결과에 영향을 미침을 알 수 있다.

$\mathrm{med}$ 값은 $B$의 크기가 $2$씩 늘어날 때마다 변함에 주목하라. $\mathrm{mex}$ 값의 증가를 위해 $0$부터 연속적으로 이을 숫자를 추가할 때, 다음 선택으로 인한 $\mathrm{med}$값의 감소를 최대한 줄이기 위해서는, 다음에는 무조건 반드시 선택되지 않았던 값들 중 최댓값을 선택해야 함을 알 수 있다. 그러므로 만약 원소를 추가할 것이라면, 둘을 동시에 추가해야만 한다.

이상을 정리하면,

• '집합' $A$에서 $i$번째로 큰 값을 $M_i$
• $m=\lfloor\frac{N}{2}\rfloor$

라 했을 때, $A$의 부분집합 $B$에 대해 $\mathrm{med}(B)+\mathrm{mex}(B)$는 다음 후보 중 최댓값이다.

• $B=\left\{M_1\right\}$일 때 $M_1+0$
  • $A$의 모든 원소는 서로 다르고 $|A|=N\geq2$이므로 $M_1$는 반드시 $0$이 아니다. 그러므로 $\mathrm{mex}(B)=0$.
• 추가로 만약 $0 \in A$라면, $B=\left\{0\right\}\cup\left\{M_1\right\}$일 때 $M_1+1$
• 추가로 만약 $1 \in A$라면, $B=\left\{0, 1\right\}\cup\left\{M_2, M_1\right\}$일 때 $M_2+2$
• ...
• 추가로 만약 $m-1 \in A$라면, $B=\left\{0, 1, \cdots, m-1\right\}\cup\left\{M_m, ..., M_2, M_1\right\}$일 때 $M_m+(m-1)$
• 추가로 만약 $m \in A$라면, $B=A$일 때 $\mathrm{med}(A)+m$
• 추가로 만약 $m+1 \in A$라면, $B=A$일 때 $\mathrm{med}(A)+(m+1)$
• ...
• 추가로 만약 $N-1\in A$라면, $B=A$일 때 $\mathrm{med}(A)+(N-1)$

코드 (Python)

N=int(input())
S=sorted(map(int,input().split()))
a=S[-1]
for i in range(N):
    if S[i]!=i:break
    a=max(a,S[max(N//2, N-1-i)]+i+1)
print(a)

메모리 및 시간

• 메모리: 145328 KB
• 시간: 164 ms

후기

• 지인이 만들었다는 문제라 풀게 되었다. 좋은 그리디 문제인 것 같다.