Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)

시스텟 전이다.

사실 오늘은 몸 상태가 하면 안되는 상태였는데 억지로 했더니 대회 중간에 건강 이슈가 있었다. 설명하기 좀 그러니까 대충 무언가가 역류했다까지만 설명하겠다.

그래서 내 뇌까지 같이 붕괴되었다.. 아니 E1에서 왜 HLD를 쓸 생각을 했을까?

마지막에 3분 남기고 E1을 맞았는데 이게 HLD 쓰는 구데기 풀이가 오류가 있었기 때문이다. 그냥 오일러 투어만 때리면 되는데 이걸 어떻게 1시간동안 못찾냐.. 그래도 마지막에 찾기라도 해서 다행이다.

 

A

1 개수 세기

 

B

걍 자기에서 시작하는 형태만 확인

 

C

이게 차이 수열로 만들고 나서 -1 곱하고 뒤집으면 전 상태에서 뒤집어서 차이 만들었을 때의 값이 나온다. 그래서 그냥 reverse 안하고 차이배열 만들면서 abs(sum) 최댓값 보면 된다.

 

D

E1 버리고 이거 푸는게 배점상 이득인데..

1/28 추가) 업솔빙했습니다.

루트를 하나 잡고 어떻게 해야 모두 같아질 수 있는지 생각해보자. 이런 문제는 보통 a를 고정한 상태에서 어떤식으로 해야 최적인지 보는 것이 좋다. u-v 간선에 대하여, a[u] != a[v]인데 a[u] = a[v]가 되려면 둘 중 작은 쪽에만 연산을 하는 것이 최적이므로 |a[u]-a[v]|번 연산을 해줘야 한다. 이때 a[u] < a[v]는 루트는 v로, a[u] > a[v]면 u로 잡는 것이 좋은데, 그래야 다른 정점들의 대소관계에 영향을 주지 않기 때문이다. 이렇게 생각해보면 리프부터 시작해서 값을 맞춰나가면서 최종적으로 루트까지 맞춰나가는 전략을 생각할 수 있고, 이때 최종 a[1]의 값은 결국 (초기 a[1]) + (아래 서브트리에서 1번 정점에 영향을 준 횟수)이다.

이걸 최소화하기 위해서는 결국 내려갈수록 a값이 작아져야 하며, a[i]는 i를 루트로 한 서브트리에서 max(a)로 맞추는 것이 최적이다. 이게 r에 bound되서 불가능하다면 r에라도 맞추는 것이 최적이다.

 

E1

1개만 찾으면 된다. 상대에게 max를 고르도록 유도하는 전략을 생각할 수 있는데 그럼 second max를 고르면 되지 않느냐? 라고 생각할 수 있다. 근데 second max를 골랐을 때 항상 max가 다 커버되면 그건 또 안되기 때문에 이렇게 커버될 경우 second max를 max로 바꿔주고 계속 확인하면 된다. 이게 끝인데 이걸 굳이 HLD로 하겠다고 뇌가 시켜서 망했다.