USACO 2019 December Contest > Gold
시험도 끝났겠다 오랜만에 유사코 연습을 돌렸다.
어려운 문제를 푸는 연습을 해야 할 것 같아서 셋은 골드 셋으로 골랐다. 내년에도 ICPC를 광탈하지 않기 위해서는 골~플랜디를 더 빡세게 할 필요가 있을 것 같다.
중간에 HLD 템플릿 만든 시간을 빼면 두 시간 정도 걸려서 풀었다. 확실히 유사코는 순수 애드혹/그리디의 비중은 낮고 여러 가지 자료구조와 알고리즘을 사용하는 문제가 많이 출제되는 것 같다.
18262: Milk Pumping (G1, dijkstra)
방향 그래프가 주어지고, 1번 정점에서 시작해 $n$번 정점에서 끝나는 경로 중 (경로의 유량) / (경로의 가중치 합)의 최댓값을 찾는 문제이다. 고정된 $k$에 대해 유량이 $k$ 이상이 되도록 최단 경로를 구성하려면 유량이 $k$ 이상인 간선들만을 사용해서 다익스트라 알고리즘을 돌리면 된다. $|V|, |E|$가 작고 유량의 최댓값도 작으므로 모든 $k$에 대해 시도해본 후 이 중 최댓값을 출력하면 된다.
트리의 두 정점 $u, v$를 잇는 경로 상에 $i$번 정점이 포함되어 있는지 판별하는 쿼리를 처리하는 문제이다. HLD에 머지 소트 트리와 lower_bound를 섞어서 쿼리당 $O(\log^{3}{n})$에 해결할 수 있다.
처음엔 set을 썼었지만 시간 초과가 나서 머지 소트 트리로 바꿔끼웠다. 덧셈 연산에 불필요한 복사가 많이 일어나서 그런 것 같은데 잘 모르겠다 ㅠㅠ
18264: Moortal Cowmbat (P3, DP)
우선 플로이드로 문자 $p$를 $q$로 바꾸는 최소 비용을 계산해두자. $S[1 \dots i]$를 잘 처리했으면 $S[i+1 \dots n]$의 부분문제가 남는데, 여기에서 DP를 적용할 생각을 할 수 있다.
$dp(a, i, b)$: $S[i]$를 알파벳 $a$로 결정했을 때 $S[i \dots n]$ 부분문제에 대한 최소 연산 비용이라 두자. 만약 직전 상태 $K$개에서 알파벳 $a$를 사용했다면 $b=1$이고 그렇지 않다면(앞으로 적어도 $K$개를 사용해야 한다면) $b=0$이라 둔다.
이렇게 DP 테이블을 정의하고 누적합 배열을 사용하면 상태 전이를 $O(M)$에 할 수 있다. 따라서 전체 시간복잡도 $O(M^3 + NM^2)$에 문제를 해결할 수 있다.