Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)

Dashboard - Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

+12 : -1

 

치졸한 방법으로 개인 최고 퍼포를 내고 맥레를 찍었다. 핵도 실력이지 ㅎ

 

Prob. A

$1$이 나올 때마다 부호를 바꿔준다.

 

Prob. B

일단 비둘기집을 이용해보려 했는데 construction이 잘 안 되어서 계속 뇌절했다. $n$을 $k$에 대하여 최대한 고르게 자르면 $n$이 $k$의 배수가 아닐 때 $\left \lfloor \frac{n+k-1}{k} \right \rfloor$ $n \bmod k$개, 나머지는 $\left \lfloor \frac{n-1}{k} \right \rfloor$가 된다. $n$이 $k$의 배수일 때도 뭐 비슷하고... 이제 $a_i$를 저기에 잘 끼워 넣어야 하는데, 일단 $\left \lfloor \frac{n+k-1}{k} \right \rfloor$보다 크거나 개수가 많으면 안 된다. 이제 나머지가 잘 끼워질까를 고민하다가 뇌가 굳었고, 뭔가 될 것 같아서 제출했더니 다행히 맞았다. 이때 1,500명이 풀었길래 개 망한 줄 알았지만....

 

$E$까지 풀고 보니 $B$에서 난리가 나 있었다. 그렇다. 내가 뇌절한 게 아니라 프리텟이 약해서 사풀이 무진장 통과한 것이었다. 운 좋게도 내 룸에서는 아직 대규모 학살이 시작되지 않았고, 내가 그 총을 잡았다. 레드를 포함해 12명을 빠르게 핵하면서 순위가 300등이나 올랐다.

 

Prob. C

$0100$에서 $4$가 안 되는 이유를 생각해보자. 마지막 두 경기는 더 작은 수가 이기기 때문에 그전에 $1, 2, 3$을 모두 탈락시켜야 한다. 그러나 그러기에는 경기 수가 부족하기 때문에 불가능하다. 비슷한 상황에서, 마지막으로 $1$이 등장하는 위치가 $i$라면 $i$ 이하의 수는 항상 탈락시킬 수 있다. 따라서 이 경우에 가능한 수의 개수는 $i+1$이다. 마지막 경기가 $1$인 경우는 대칭적으로 생각할 수 있다. 사실 좀 다르게 풀어서 틀린 부분이 있을 수 있다.

 

Prob. D

?? 그냥 시간복잡도 유지되게만 잘 구현하면 된다.

 

Prob. E

dfs 한 번으로 각 피스의 각 노드마다 내려가야 하는 최대 깊이를 전처리한다. 그리고 다시 dfs를 돌면서 두 피스가 모두 내려가야 하는지, 하나만 내려가도 되는지를 따져주면서 재귀적으로 답을 구해주면 된다.