USACO 2018 US Open Contest > Silver
[공지]
https://www.acmicpc.net/group/21869
USACO 셋을 밀려고 하는데, 혼자 하긴 적적해서 그룹을 만들었어요!
매주 수/금/일 오후에 그룹 내 연습으로 silver~gold 수준의 셋 한 개를 돌아볼 예정입니다.
(제 개인 사정으로 몇 번 건너뛸 수도..😢)
열심히 하실 분 / 찍먹 하실 분 / 관전만 하실 분들 모두 환영입니다..!
오늘은 2018년 US Open (왜 거창하게 us-open이지..?) silver 셋을 돌렸다. 원래 9시 즈음에 시작하려 했으나 치킨이 일찍 오는 바람에 두 시간 늦춰서 문제를 풀었다 ㅎ
시간 안에 올솔했고 재밌는 셋이였던 것 같다!
15760: Out of Sorts (G1, 정렬, 좌표 압축)
버블 정렬을 배열의 전체 범위에서 수행하는데, 몇 바퀴를 돌지를 구하는 문제이다. 고정된 $i$에 대해 $a_j > a_i$이고 $j < i$인 $j$가 $k_i$개 존재한다고 하자. 매 step에서 $k_i$는 정확히 1씩 줄어든다. 어쨌거나 $a_i$와 $a_i$보다 작은 원소의 교환은 단 한 번 일어날 것이기 때문이다. 따라서 inversion counting 느낌으로 세그먼트 트리를 이용해 모든 $i$에 대해 $k_i$값을 구해주고, 이 중에 최댓값+1이 답이 된다.
수의 범위가 커서 좌표 압축을 사용했다. 사실 그냥 좌표 압축 후 정렬만 해 주면 풀리는 것 같다.
15761: Lemonade Line (S4, 그리디, 정렬)
Exchange argument를 사용하자. 최적해에서 제일 큰 원소를 앞으로 빼도 최적임에는 변함이 없다. 따라서 그냥 역순으로 정렬하고 몇 마리까지 레몬에이드를 먹을 수 있는지 계산하면 된다.
15762: Multiplater Moo (P3, 그래프 이론, 유니온 파인드)
구하고자 하는 첫 번째 값은 최대 컴포넌트의 크기로, 쉽게 구할 수 있다. 두 번째 값은 어떻게 구할까? 인접하고 id가 같은 칸들을 하나의 노드로 묶어 그래프로 모델링해보자. 임의의 두 id를 골라서 두 개의 id만으로 이루어진 컴포넌트 크기의 최댓값을 구해야 한다. 비효율적으로 구현하면 시간복잡도가 $O(N^6)$으로, 잘 최적화할 방법을 찾아야 한다.
관찰을 통해, 모델링한 그래프의 간선은 최대 $O(N^2)$개임을 알 수 있다. 각 칸마다 네 방향으로 탐색해서 간선을 이어 주기 때문이다. 또한 정의에 의해 어떤 간선은 두 id가 다른 노드를 잇는다.
따라서 id 대신 모든 존재하는 간선을 기준으로 하여 순회할 생각을 해볼 수 있다.
map<pair, vector<pair>>같은 자료구조를 사용해서 연결돼있는 노드의 id에 따라 간선을 분류하자. Map의 각 원소를 순회하면서, 등장하는 간선에 붙어있는 노드를 union find로 합치고, 이 중 최대 컴포넌트의 크기를 구한다. 이 때 한 컴포넌트를 여러 다른 간선이 이을 수 있으므로 매 step마다 union find를 효율적으로 초기화시켜줘야 한다. 이렇게 $O(N^2\log{N})$의 시간복잡도로 문제를 해결할 수 있다.