CodeForces Round 940 - Div 2

 

https://codeforces.com/contest/1957

 

 

 

Performance Rating : 2350

 

A

$a_i$를 입력받으면서 개수를 저장해 두고 저장된 개수에 3을 나눠서 더하는 문제였다.

 

B

$k$를 이진수로 나타냈을 때 $x$자리수라고 했을 때 1이 $x$개라면 $k$ 하나만 출력하면 되고 $x$개보다 작다면 $2^x-1$, $k-x$, x$, 나머지를 $0$으로 채우면 되는데 이는 $1$의 개수가 $x$개일 때에도 적용할 수 있어 $n$이 1일 때에만 예외처리를 해주고 구현했다.

 

C

최종 상태는 하나의 행에 하나씩의 룩이 배치된다. 또한 지금까지 결정된 열이 $p$개라고 하면 $(n-p)\times (n-p)$ 판에 룩을 채우는 경우의 수와 같다. 각 경우에 대해 $p$를 구해주고 $i\times i$ 판에 룩을 배치하는 경우의 수를 구해놓아 답을 구할 생각을 했다. $dp[i]$를 $i\times i$ 판에 룩을 배치하는 경우의 수라고 정의하면 $dp[i]=dp[i-1]+2(i-1)dp[i-2]$가 된다. 첫 번째 열 중 어느 곳에 룩이 배치되는지와 룩의 색깔을 기반으로 구한 것이다. 이제 $p$만 구하면 되는데, $r_i=c_i$인 경우 1을 더하고 아니면 2를 더하면 된다.

 

D

결국 $a_y\oplus f(x, z) > f(x, z)$인 $(x, y, z)$의 개수를 구하면 된다. $a_y$의 최상위 비트가 $f(x, z)$에서 1이라면 $a_y\oplus f(x, z) < f(x, z)$이고, 아니라면 $a_y\oplus f(x, z) > f(x, z)$이다. 이제 구해야 하는 것은 $x\leq y\leq z$인 $(x, z)$ 중 $f(x, z)$의 $lg(a_y)$번째 비트가 0인 것의 개수이다. 이는 $a_x,\cdots,a_z$ 중 $lg(a_y)$번째 비트가 1인 숫자의 개수가  짝수개여야 하는데 이는 비트별로 누적합을 통해 구했다.

 

E

버추얼 도중에는 풀지 못했고 끝난 뒤에 업솔빙을 했다. $C(i, j)=(j-1)!\binom{i}{j}$이다. $(j-1)!\binom{i}{j}\;\mathrm{mod}\;j$의 값이 어떻게 될지 생각해 보았다. 우선 $j$가 4가 아닌 합성수일 경우 $C(i,j)\; \mathrm{mod}\;j$의 값이 0이 되는 것을 확인했다. 그 후 $j$가 소수일 경우는 $i$의 값 별로 규칙을 찾아 레이지 세그먼트 트리를 활용해 값을 업데이트해둔 뒤 답을 출력했다.