Codeforces Global Round 5 후기
나는 야호다.
버추얼하나 까서 요약남김
A. Balanced Rating Changes
제로 섬인 배열이 주어졌을때 이를 각각 /2를 하는데, 짝수의 경우는 그냥 /2를 하면되고 홀수의 경우 floor(a/2)와 ceiling(a/2)를 번갈아 하면 된다.
O(n)
B. Balanced Tunnel
Ai를 처음에 i번째로 들어온 자동차가 터널을 통과한 등수라고 하자.
A1~ai-1중의 최대값이 ai보다 크면, 이 차는 자기보다 먼저 통과한 차량중 최대값의 차량을 추월한 것이 된다.
잘 이걸 계산하면 된다.
O(n)
C. Balanced Removals
만약 1차원의 경우라면, 가까운 녀석들 끼리 매칭시키면 끝.
2차원의 경우라면, 각 x좌표별로 1차원의 매칭을 진행한후 남은 데이터끼리 x좌표가 가까운 두개끼리 매칭하면 끝
3차원의 경우라면 각 x좌표별로 2차원의 매칭을 진행한 후 남은 데이터끼리 x좌표가 가까운 두개끼리 매칭하면 끝이다.
이를 재귀로 잘 구현하면 된다. 나는 map<int, vector<int>>를 이용하여 관리했다.
O(nlogn) d차원의 경우에도 O(dnlogn)이면 될듯
D. Balanced Playlist
최대값을 빠르게 찾을수 있는 자료구조에, 노래들을 순서대로 넣으면서 못넣는 노래가 나오면 오래된노래부터 하나씩 빼버려서 못넣는 노래를 넣을수 있을때까지 반복한다.
이때 자료구조에서 빠지는 노래는 현재 노래를 넣으려고 할때 실행이 멈추게 되는 것이므로 노래를 뺄때 현재 자료구조에 있는 데이터 개수을 기록. 이를 모든 노래에 반복하면 된다.
반복횟수가 일정이상 넘어가면 모든 노래가 무한반복되니 예외처리를 하자.
위에 해당하는 자료구조로 set을 쓸수 있으나 priority queue 두개로 하면 더 빠르게 계산이 가능하다.
O(nlogn)
E. Balanced Binary Search Trees
낚시문제다. 설마 E에 낚시문제가 나오겠어? 를 노린 양아치문제.
약간의 관찰을 통해서 striped라는 조건이 매우 strict한 조건임을 알수 있고 소수로 나눈 나머지를 구하라고 했지만 가능한 트리가 존재한다면 유일하게 존재하는 것을 캐치하면 끝(답이 0또는 1이라는 뜻)
가능한지는 재귀적으로 구하면 되는데 어떤 tree 가 주어진 조건을 만족하려면 tree의 root에서 striped property를 만족하고 왼쪽 자식 오른쪽 자식이 모두 주어진 조건을 만족하면 된다.
그 후 작은 input에 대해 그려보고 규칙을 찾아서 풀었다. 여기까지 왔다면 규칙은 생각보다 찾기 어렵지 않으니 독자에게 남긴다. 대신 코드를 첨부.
O(logn)
FGH모름 ㅅㄱ