오전 셋

어제 밤에 돌았던 CSAcademy Round 84 (a.k.a koosaga round)이다.

그래서 어제 2시반쯤 자서 오늘 오전에는 쭉 잤다.

그나저나 CSA 되게 좋더라. 별로인줄 알았는데 계속 해봐야겠다.

 

A. Douchebag Parking

B. Three Ones

C. Split the Sticks

정렬한 후 짝수는 반으로, 홀수는 두개씩 묶어서 하면 된다.

D. Manhattan Center

봐야 하는 좌표는 각 점의 x좌표들 뿐이다.

각 좌표를 자나면서 점들을 [아직 안쓴거, 쓴것중 내 오른쪽, 쓴것중 내 왼쪽, 버린거] 로 나누어 셋이나 PQ같은걸로 관리하면 된다.

다른 사람들은 각 죄표별로 왼쪽 K/2, 오른쪽 K-K/2로 해서 하기도 했다더라, 그러면 좀 더 편할수도.

E. Growing Trees

보고 ???해서 넘겼었다.

N^2개의 경로를 전부 시간 - 가중치 그래프를 그려보면, 그중에서 최대값만 신경쓰면 된다. 직선들이니까 최대값은 적당하게 삼분/이분탐색할 수 있게 나온다.

F. The Sprawl

맨해튼 거리 공간에서 MST를 구하는 걸 생각해보면, 가중치 c인 간선이 집합 A와 B를 연결한다고 하면 c* A * B 를 전부 더해주면 된다.

맨해튼 거리 공간에서 MST를 구하는 건 8방으로 가장 가까운 점들과 연결하는 것만 고려하면 되고, 이건 돌리고 뒤집으면서 스위핑을 하면 된다.

G. Baby Seokhwan

아기석환 뚜루룻뚜루

모른다.

오후 셋

AGC중에서 어려운 걸 골라서 돌았다.

AGC18D Tree and Hamilton Path

센트로이드에서 시작해서 한 간선만 제외하고 전부 최적으로 돌 수 있다. 적당히 계산해주면 된다.

AGC17E Jigsaw

퍼즐의 오른쪽 끝의 상태가 많아야 2H가지이다. 따라서 정점을 2H개 만들고 유향 그래프를 그릴 수 있고, 특정한 H개 정점중 하나에서 시작해서 다른 H개 정점중 하나에서 끝나는 경로들로 분해가 되면 가능하고, 안되면 불가능하다.

일단 그래프를 그린 후, 시작점이여야 하는 정점 집합을 A, 도착점이여야 하는 정점 집합을 B라고 하자. A에서 indeg가 더 크거나, B에서 outdeg가 더 크면 불가능하다.

만약 한 컴포넌트가 전부 A에, 아니면 전부 B에 속해 있다면 경로를 만들 수 없으니 불가능하다.

그 외의 경우는 모두 가능하다. 따라서 적당한 union-find와 indeg,outdeg만 잘 세주면 판별 가능하다.

AGC12F Prefix Median

한 수열의 중간값 배열이 가지는 특성이 있다고 한다. 대충: 1. 중간값의 범위 2. 인접한 중간값들의 관계에 대한 것이다.

사실 저 특성이 필충조건이라고 한다. 그래서 저걸 바탕으로 DP를 세울 수 있다. N^4이라고 한다.

AGC18F Two Trees

패리티가 정해지므로, 두 트리에서 같은 번호를 가진 정점에 대해서 자식 수가 다르면 안된다.

그리고 모두 같으면 되도록 아래와의 같은 방법으로 Xi를 매길 수 있다.

두가지 풀이가 있다.

정점을 2N+1개 가진 새로운 그래프를 적당히 그려서 모든 점의 차수가 짝수가 되도록 한 후, 오일러 사이클을 따라 간선에 방향을 주고 계산하는 식으로 Xi를 정해줄 수 있다. 고 하는데 잘 모르겠다. imeimi와 출제자의 풀이이다.

자식 수가 홀수인 점은 모두 0, 짝수인 점은 +-1로 정해줄 것이다.

한 서브트리 아래의 짝수점이 항상 홀수개인데, 그래서 걔네들을 적당히 두개씩 이어준다. 이걸 A트리에서도, B트리에서도 한다.

그러고 나서 이어준 것만 보면 홀수 사이클이 없는 여러개의 컴포넌트가 나온다. 그러니 인접한 정점의 X값이 다르도록 부호를 바꿔가면서 주면 된다.