Codeforces Round #845 (Div. 2)

Dashboard - Codeforces Round #845 (Div. 2) and ByteRace 2023 - Codeforces

 

PS 재활 시작...!

 

Prob. A

연산을 한 번 할 때마다 패리티가 같은 인접한 쌍이 하나 사라진다. 따라서 패리티가 같은 인접한 쌍의 수를 세주면 된다.

 

Prob. B

아직 심층식 사고가 남아있는 탓인지 $(1, 2, \cdots , n-1)$에 $n$을 추가하는 식으로 생각했다. 이걸 이용하면 조합론 DP를 할 수 있는데 뇌절이고, 전체적인 구조만 살펴보면 $n \times (n-1) \times n!$이 답이라는 걸 알아낼 수 있다.

 

Prob. C

풀이는 뻔하다. 대충 정렬하면 가운데에 위치한 놈들은 다 쓰는 게 이득이니까 투포인터를 잘 굴려주면 된다. 약수는 에라체를 이용해서 잘 전처리하자.

 

Prob. D

구하라는 게 복잡하니 자연스럽게 더블 카운팅을 떠올릴 수 있다. 각 노드가 정답에 얼마나 기여하는지를 생각해주면 되는데, 이것도 쉽지 않으니 대충 기댓값을 구하고 $2^n$을 곱해주자는 발상을 할 수 있다. 리프 노드부터 기댓값을 생각해보면 $0.5$가 차례로 더해지는 형태이니 dfs로 리프로부터 최대로 떨어진 거리를 구해주면 된다.