레이팅 미적용설명
음이 아닌 정수 \(N\)개로 이루어진 배열 \(a\), 즉 \(a_1, a_2, \dots, a_N\)(\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\))이 주어진다. 한 번의 연산으로 \(a\)의 임의의 원소를 임의의 음이 아닌 정수로 바꿀 수 있다.
배열의 mex는 그 배열에 포함되어 있지 않은 가장 작은 음이 아닌 정수이다. \(0\)부터 \(N\)까지(양 끝 포함)의 각 \(i\)에 대해, \(a\)의 mex가 \(i\)가 되도록 만들기 위해 필요한 연산의 최소 횟수를 계산하시오.
Problem credits: Benjamin Qi
제약
배점
- 입력 2-6: \(N\le 10^3\)
- 입력 7-11: 추가 제약이 없다.
Problem credits: Benjamin Qi
입력 형식
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(a_1,a_2,\dots, a_N\)이 주어진다.
출력 형식
\(0\)부터 \(N\)까지의 각 \(i\)에 대해, \(i\)에 대한 최소 연산 횟수를 새로운 줄에 출력한다. \(0\)부터 \(N\)까지의 어떤 \(i\)에 대해서도 \(a\)의 mex를 \(i\)로 만드는 것이 항상 가능하다는 점에 유의하라.
예제 1
입력
4
2 2 2 0출력
1
0
3
1
2설명
- To make the mex of \(a\) equal to \(0\), we can change \(a_4\) to \(3\) (or any positive integer). In the resulting array, \([2, 2, 2, 3]\), \(0\) is the smallest non-negative integer that the array does not contain, so \(0\) is the mex of the array.
- To make the mex of \(a\) equal to \(1\), we don't need to make any changes since \(1\) is already the smallest non-negative integer that \(a = [2, 2, 2, 0]\) does not contain.
- To make the mex of \(a\) equal to \(2\), we need to change the first three elements of \(a\). For example, we can change \(a\) to be \([3, 1, 1, 0]\).
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Bronze
태그