editorial

editorial of c

---

C

summary:

자연수 집합이 있는데, 매일 $a_1, a_2, \dots, a_n$ 번째의 수들을 없앤다.

$k$일 이후 첫번째 원소가 무엇인지 구하는 문제이다.

solution:

어떤 수가 집합의 최솟값이 되려면 마지막 날에 그 수 앞에 남아있는 수가 하나도 없어야 한다.

$x$일에 남아있는 집합의 첫 수를 $ans_x$라고 하자.

$a_i < ans_x+i < a_{i+1}$ 이면 $ans_{x+1}$는 다음날 $ans_x+i$가 된다. $ans_x+i$의 입장에서 자기 앞에서 뭐가 없어졌는지는 몰라도 $i$개가 줄어들기 때문이다.

첫째 수 $ans_1=mex(a)$이고, $ans_x$보다 큰 $a_{i+1}-1$까지 $i$개씩 가능한 최대 개수를 빼면서 $k$일째 $ans_k$를 구하면 된다 .

D

summary:

모든 원소가 0이상의 값을 가지는 $a$가 주어질 때, 다음을 만족하는 배열 $b$를 구하는 문제이다.

$−n \le bi \le n, b_i \neq 0$

there are no two indices $(i,j) (1 \le i,j \le n)$ such that $b_i+b_j=0$

for each $(1 \le i \le n)$, there are exactly $a_i$ indices $j(1 \le j \le n)$ such that $(bi+bj>0)$, where $i$ and $j$ are not necessarily distinct.

solution:

$b$의 모든 원소는 $(-1,1), (-2,2), \dots, (-n,n)$중에서 하나의 값으로 결정된다.

먼저 a를 덱으로 만들고 정렬한 다음, 현재까지 결정된 b의 원소 중 양수의 개수를 pos라고 하자.

$min(a)-pos=l$ $max(a)-pos=r$이라고 하면, $l=0$이거나 $r=size(a)$이다. 그렇지 않으면 $b$를 구성할수 없다.

$l<0$이거나 $r>size(a)$인 경우에도 $b$를 구성할수 없다.

$pos$를 빼는 이유는 자신보다 절댓값이 큰 양수와 더하면 자신이 될 수와 상관없이 양수가 되기 때문이다.

$l=0$이면 해당 수는 $-size(a)$이고, $r=size(a)$이면 해당 수는 $size(a)$이다.

$a$가 빌때까지 반복하면 된다.