제2회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE 2020
백준20309 트리플 소트
홀수 번째 원소는 짝수 번째로 이동할 수 없고, 짝수 번째 원소도 홀수 번째로 이동할 수 없습니다.
$i \equiv A_i \mod 2$인지 확인하면 됩니다.
백준20310 타노스
0은 뒤에 있는 것을 제거하는 것이 이득이고, 1은 앞에 있는 것을 제거하는 것이 이득입니다.
백준20311 화학 실험
어떤 색이 $(N+1)/2$개보다 많이 있으면 불가능하고, 그렇지 않은 경우 항상 가능합니다.
개수가 가장 많은 색부터 1 3 5 7 ... 2 4 6 8 ...순으로 배치하면 됩니다.
백준20312 CPU 벤치마킹
각 행마다 어떤 수가 적히는지 생각해봅시다.
- 아무것도 안 적힌다.
- $A_1$
- $A_1A_2, A_2$
- $A_1A_2A_3, A_2A_3, A_3$
$S_i$를 $(i+1)$번째 행에 적힌 수의 합이라고 하면, $S_i = (S_{i-1} + 1) \times A_i$가 됩니다.
간단한 DP 문제입니다.
백준20313 출퇴근
각 정점을 $(K+1)$개씩 만들어서 다익스트라를 돌리면 됩니다.
백준20314 대홍수
$L_i, R_i$를 각각 $i$번째 사람이 갈 수 있는 가장 왼쪽 / 오른쪽 지점이라고 합시다.
$L_i \leq L_{i+1}, R_{i-1} \leq R_i$를 만족하기 때문에 투포인터를 이용해 $O(N)$에 구할 수 있습니다.
갈 수 있는 구간 내에서 최대 높이는 세그먼트 트리를 이용해 구하면 됩니다.
백준20315 야바위
각 쿼리마다 구슬의 최종 위치만 알면 됩니다.
오프라인으로 문제를 해결합시다. $S_i$번째 컵(std::set)에 $i$번째 구슬을 넣고, 구슬을 이동시킬 것입니다.
윤이가 본 $N-1$개의 동작은 지문에 나와있는대로 처리하면 되고, 이후 주어진 $M$개의 동작은 해당하는 구슬만 이동시키면 됩니다.
그대로 시뮬레이션을 하다보면 두 set을 합치는 상황이 나오는데, 작은 set에 있는 원소를 큰 set으로 옮겨주면 각 구슬은 최대 $O(\log M)$번 이동하므로 빠르게 수행할 수 있습니다.
쿼리를 정렬하는데 $O((N+M) \log (N+M))$, 쿼리를 처리하는데 $O(M \log^2 M)$이 걸리므로 시간 내에 문제를 해결할 수 있습니다.