[2020-09-12] Codeforces Round 572 (Div.1)

이제는 뭐 기대를 하면 안 될 것 같애.. 

조만간 퍼플로 내려가겠다.

A1. Add on a Tree

문제를 잘 정리해보면, degree = 2 인 노드가 하나라도 있으면 불가능하다. degree 2인 트리에서 양쪽 리프를 하나씩 잡으면 해당 두 엣지에 항상 같은 값이 추가되는데, 이 때문에 이 양쪽 엣지에 다른 값이 들어가있는 경우 생성이 불가능.

A2. Add on a Tree: Revolution

B가 수식을 잘 조정해서 푸는 문제였는데 못 풀겠어서 A2만 한참을 붙잡았다. 근데 못 풀었다.. 문제에서 주어진 조건을 좀 더 잘 활용해서 유연하게 생각했어야 했는데 그걸 못 했다. 왜 이렇게 생각이 빨리빨리 안 돌아가는지..

 

모든 값이 짝수 / 서로 다르다는 점을 생각해보자. 모든 엣지에 들어가있는 값이 다르기 때문에 A1처럼 degree 2인 노드가 있으면 불가능하다. 그게 아닌 경우 항상 가능한데, 어떻게 가능한지 생각해보자.

 

임의의 u - v에 값 x를 더해야 하는 경우, u의 서브트리에 있는 리프노드 a, b 두 개를 골라서 path a ~ v 에 + x / 2, b ~ v에 + x / 2,  a ~ b에 - x / 2를 해주면 u - v에 +x를 해줄 수 있다. u가 리프면 그냥 u ~ v에 + x를 해주면 된다. 이 때 v도 문제 조건상 리프여야 하는데, 전체 트리의 루트를 리프노드(edge 개수 = 1)로 잡고, 루트까지 전부 다 값을 +x 해주는 식으로 만들면 재귀적으로 올라오면서 쉽게 계산할 수 있다.

B. Count Pairs

어떻게 보면 대놓고 수식이 있는 거였는데 생각을 못 했다. 너무 빨리 포기를 한 것 같다.. 뭔가 이렇게 수식에 요리조리 작업을 해야하는 경우 잘 못 푸는 듯. 양 변에 (a_i - a_j) 를 곱해준 다음 수식을 정리해보면 양쪽 변의 형태를 똑같게 맞춰줄 수 있다. 이렇게 바꾸면 결국 주어진 배열에서 같은 값이 있는 위치 둘을 고르면 조건을 만족한다는 뜻이 되므로, map등을 이용해 계산할 수 있다. 엄청 자주 쓰이는 곱셈 공식인데 왜 이걸 생각을 못 했을까.. B가 척 봐도 수학이라 잡는게 걱정됐고, A2가 좀 풀릴 것 같아 보여서 A2에 너무 집착한 것도 문제인 것 같다.