TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

Dashboard - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

 

D에서 말려서 대회 던질 뻔 했다가 E를 빠르게 풀고 기사회생했다.

 

Prob. A

일단 하나에 1을 넣어보면 $n$이 짝수일 때 다른 하나로 $\frac{n}{2}$이 가능하다는 걸 알 수 있고, 예제를 보면 $n$이 홀수일 때 불가능하다는 것을 추측할 수 있다. 대충 기우성으로 증명할 수 있겠지.

여담으로 0분대 솔브가 나 포함 5명 밖에 안 돼서 순간 누텔라 퍼포를 찍었다.

 

Prob. B

잘 생각해보면 $a_i$를 크게, $p_i$는 작게 만드는 것이 최적이므로 루트 시간에 소인수분해를 하고, 소인수 개수로 정렬한 후 그리디하게 최대한 많이 곱해주는 것을 반복하면 된다.

 

Prob. C

재배열 부등식 비슷하게 생겼다. 이런 거는 보통 수를 한 쪽으로 몰아주는 것이 최적이기 때문에 $a_i$를 그렇게 나눠주고 DP를 돌려주면 된다.

 

Prob. D

$1$부터 시작해서 그래프를 따라갈 때 만나는 노드들 말고는 $1$에 영향을 줄 수 없다. $1$이 결국 루프에 빠지냐 탈출하냐에 따라서 더해주어야 하는 값이 달라지는데, 전자는 전체 노드 중 루프에 빠지는 노드의 수가 필요하고 후자는 이것과 역방향 트리의 서브트리의 크기가 필요하다.

 

Prob. E

$k$가 홀수일 때는 전체 xor이 $x$, $k$가 짝수일 때는 전체 xor이 $0$인 것이 기본 성립 조건이다. 홀수 개의 그룹은 하나로 합칠 수 있다는 점에서, 일단 최대한 많은 그룹으로 분할하는 것이 이득이다. 그룹 개수가 넘치면 적당히 합쳐주면 되기 때문이다. 이제 어떻게 나눌 것이냐 보면, 크기가 2 이하인 그룹 중 가능한 것을 모두 만들어주고 나머지를 하나로 합쳐주면 된다. 이게 최적임은 비둘기집의 원리 비슷하게 증명이 되는 것 같은데, 대회 중에는 고민하지 않았다.