CodeForces Educational Round 177

https://codeforces.com/contest/2086

 

 

Performance Rating : 2850

 

A

$n$을 입력받고 $2n$을 출력하는 문제였다.

 

B

$r$은 $nk$에 고정해 두고 가능한 $l$의 최댓값을 구하면 된다. 반복이 된다는 점을 활용하여 $b_l+\cdots+b_{nk}\geq x$인 $l$의 최댓값을 구했다.

 

C

관찰을 하다가 특정 숫자를 고치기 시작하면 순열 사이클 분할을 해놓은 모든 숫자들을 다 고쳐야 한다는 것을 알게 되었다. 쿼리별로 입력을 받은 뒤 이미 끝난 숫자라면 답을 출력하고 아니라면 순열 사이클을 찾아 개수를 답에 더해주었다.

 

D

홀수 인덱스를 가진 부분과 짝수 인덱스를 가진 부분이 정확히 분리되어 있다는 생각을 했다. 우선 알파벳들의 분배를 적절히 잘했을 경우 각 분배별로 몇 가지의 경우의 수가 있는지 관찰을 했다. 알파벳 분배 별 경우의 수는 $ \frac{((n+1)/2)!(n/2)!}{\prod c_i!}$라는 것을 확인한 뒤 분배의 경우의 수를 $dp$로 구할 생각을 했다. 분배의 경우의 수는 두 그룹의 알파벳 개수 차이를 바탕으로 $dp$를 통해 구했다.

 

E

1부터 $r$까지의 답을 구하는 함수를 구하고 $cnt(r, x)-cnt(l - 1, x)$을 통해 답을 구하면 되겠다는 생각이 먼저 들었다. 이제 $calc(r, x)$를 어떻게 구할지 생각을 하면서 관찰해 보니 큰 것을 사용할 수 있다면 무조건 사용하는 것이 좋을 것 같았다. 또한 $k$의 범위가 $10^{18}$이지만 적어도 $200$개 이상이 필요한 숫자가 없다는 결론을 내렸다. $dp$로 $cnt$ 함수의 값을 구할 생각을 하고 $dp[i][j]$를 $z_i$이하의 수 중 zebra number가 $j$인 숫자의 개수이다. 그러면 $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]$이 된다. $dp$를 미리 구해놓으면 $cnt(r,x)$를 구할 때 $r$에서 $z_i$를 빼고, $x$에서 1을 빼가면서 $dp[i][x]$를 더하면 답을 구할 수 있다.