Codeforces Round 1006 - Div 3

https://codeforces.com/contest/2072
 

 
Performance Rating : 2450
 
A
절댓값이 $p$이하인 수 $n$개로 합이 $k$가 되게 할 수 있는지 판단하고 만들 수 있을 때 필요한 수의 최소 개수를 구하는 문제였다. $\mathrm{abs}(k)\leq np$인지 먼저 판별하고 맞다면 $(\mathrm{abs}(k)+p-1)/p$개가 최소이다.
 
B
'-'를 양끝으로 몰고 '_'를 가운데에 배치하고 양끝의 '-'개수를 최대한 동일하게 맞추는 것이 최선이다. '-'의 개수를 $cnt_1$, '_'의 개수를 $cnt_2$라고 하면 $(cnt_1/2)((cnt_1+1)/2)cnt_2$가 답이 된다.
 
 C
일단 0부터 시작해서 최대한 큰 숫자까지 쓰고 bitwise or을 해주었을 때 $x$가 되도록 만들어주어야 한다. 일단 이진법으로 나타냈을 때 $x$의 $p$번째 자리가 0이라면 $2^x$는 $a_i$에 절대 등장할 수 없다. 그러므로 0번째 자리부터 시작해서 가장 먼저 등장하는 0의 자릿수를 $id$라고 하면 $\mathrm{MEX}({a_1,\cdots,a_n})$값은 $2^{id}$이상이 되는 것이 불가능하다. 그러므로 $2^{id}$와 $n$의 값을 비교하여 0부터 넣을 수 있는 최대한 많은 숫자를 넣어준 뒤 $x$를 남는 개수만큼 출력해 주면 된다. 여기서 $2^{id}>n$이더라도 $0$부터 $(n-1)$까지 bitwise or한 값이 $x$인 경우에는 그냥 0부터 $(n-1)$까지 출력해주면 된다.
 
D
$n$의 제한이 2000이므로 모든 $(l,r)$쌍에 대해 살펴보는 것이 가능하다는 생각을 먼저 했다. inversion counting은 모든 $i$에 대해 $a_i$보다 앞에 있는 $a_i$보다 큰 값의 개수가 중요하므로 $a_l$을 $a_r$자리로 옮긴 경우 $a_{l+1},\cdots,a_r$ 중 $a_l$보다 작은 것의 개수를 $cnt_1$에 저장하고 큰 것의 개수를 $cnt_2$에 저장하여 $cnt_1-cnt_2$가 최대인 $l$, $r$을 찾아주면 된다.
 
E
피타고라스 거리와 택시 거리가 같기 위한 조건은 $x$좌표나 $y$좌표가 같은 것이기 때문에 $x$좌표가 같도록 고정을 해놓고 필요한 개수만큼의 $y$좌표를 해당 $x$좌표에 할당해 주기로 했다. $k$보다 $p(p-1)/2$가 작거나 같은 최대 $p$를 찾고 $k$에서 $p(p-1)/2$를 빼주고 $x$좌표 하나에 $p$개의 $y$좌표를 할당해 출력해 주면 된다. 여기서 $y$좌표가 같은 쌍이 없도록 해주어야 한다.
 
F
그림을 그려 규칙을 찾았고 이를 재귀로 구현했다.. $n=2^x$인 경우 $n$개의 $k$가 나오고 아닌 경우 $n>2^x$인 최대 $x$를 찾고 양쪽에 $(n-2^x)$일 때 패턴을 출력하고 가운데에는 $(2^{x+1}-n)$개의 0을 출력하면 된다.
 
G
처음에 문제를 보고 $n$이하의 모든 경우를 다 해보는 것이 $O(nlogn)$이라서 매우 쉬운 문제라고 착각했으나 $t$가 5000이라는 제한 때문에 TLE를 한번 받았다. 이후 복잡도를 $O(sqrt(n))$으로 줄일 생각을 했다. 복잡도를 줄이기 위해서는 $n$을 $p$진법으로 나타냈을 때 두 자리가 되는 경우를 분리할 필요가 있어 보였고 $n\geq p^2$인 $p$에 대해서는 그냥 계산해 주고 $n<p^2$인 $p$에 대해서는 앞자리가 같은 것끼리 묶어 계산해 주었다.