[Codeforces] Round #509

http://codeforces.com/contest/1041

 

문제 난이도가 적당히 쉬운 편이었습니다. C번 해석이 잘 안되어서 시간을 날린게 좀 아깝습니다.

 

A - Heist (Code)

 

그냥 min element와 max element의 차이만 계산한 후에 길이를 가지고 이리저리 식을 만들면 됩니다.

 

B - Buying a TV Set (Code)

 

적당한 상수 k에 대해 $w = xk$, $h = yk$이면 해당조건을 만족합니다. 이 때 x, y를 gcd(x, y)로 미리 나눠두어야 합니다. 이후엔 주어진 크기 범위에 있는 갯수를 체크하면 됩니다.

 

C - Coffee Break (Code)

 

맨 처음엔 문제가 무슨 소리인가 이해가 전혀 가지 않아 헤맸네요. 2018 SCPC 예선문제인 버스 타기와 유사합니다. 우선 d일 이내로 붙어있는 최장 구간의 길이를 찾아 필요로하는 날 수를 구하고, 그 후에 쉬는 날짜는 greedy하게 부여하면 됩니다.

 

D - glider (Code)

 

Ascending air flow가 시작하는 곳에서 출발하는 것이 가장 멀리갈 수 있는 길임은 쉽게 증명이 가능합니다. 그러면 이제 N개의 가능한 시작점에서 모두 점프를 뛰어보면 되는데, 각 시작점에 대해 내가 탈 수 있는 가장 마지막의 air flow를 binary search로 O(lg N)에 구할 수 있으므로 O(NlgN)에 해결이 가능합니다. C를 건너뛰고 D로 바로 넘어왔는데 코딩에서 살짝 꼬여서 시간을 지체했습니다.

 

E - Tree Reconstruction (Code)

 

문제가 정말 흥미로웠습니다. 우선 모든 조합에 N이 있어야함은 자명합니다. 이제 N을 root로 생각해봅시다. 각 간선을 절단하면 subtree의 일부와 나머지 영역(최대값이 N임)으로 절단이 됩니다. 이제 N-1을 생각해보면, N-1이 k번 등장했다는 얘기는 N과 N-1 사이에 간선이 k개 존재한다는 뜻입니다. 즉 N의 depth를 0이라고 했을 때 N-1의 depth는 k라는 것이죠. 그리고 그 사이에 있는 수는 무엇이 오든 아무 상관이 없습니다. 이후 N-2가 등장하지 않는다면 N에서 N-1로 가는 경로에 N-2가 등장하는거고 a번 등장한다면 마찬가지 논리로 N-2의 depth는 a임을 알 수 있습니다. 이런 식으로 construction을 하면 됩니다.