구사과

최소 스패닝 트리 (MST) 는 무방향 그래프에서만 정의되는데, 방향 그래프에서도 MST 비슷한 것을 정의하기도 합니다. Minimum Arborescence 이라고도 부르는데, 방향 그래프 $G$ 와 루트 정점 $r$이 주어졌을 때 무방향 그래프로 봤을 때 사이클이 없고 $r$ 에서 모든 정점을 도달 가능하면 이를 $r$ 을 루트로 한 Directed MST라고 합니다. 루트 정점을 무조건 정의해 줘야 함에 주의해야합니다. 이 글에서는 Chu–Liu/Edmonds' algorithm 이라고 불리는, Directed MST를 구하는 알고리즘을 간단히 소개합니다. 일반적으로 $O(VE)$ 시간 복잡도에 해결하는 방법을 사용하는데, 여기서는 $O((V + E) \log E)$ 에 문제를 해결할 것입니다. 다..

NAC 2020 F. Hopscotch 50 간단한 DP 입니다. $dp[i][j]$ 를 $(i, j)$ 셀에 도착하는 최소 비용이라고 합시다. 만약 이 셀에 1이 적혀 있으면 답은 0입니다. 아니면, 이 셀보다 적힌 숫자가 1 작은 모든 셀 $(k, l)$ 이 이 셀로 들어오는 것이 가능한 후보가 됩니다. 모든 후보 중 $dp[k][l] + |k-i| +|l-j|$ 값의 최소를 취해주면 됩니다. 이대로 구현하면 시간 복잡도는 $O(N^4)$ 입니다. Ptz Winter 2019 Day7 G. Permutant 주어진 순열이 2개 이상의 사이클을 포함하고 있다면, 답은 0이 됩니다. 주어진 순열이 “정확히 2개” 의 사이클을 포함하고 있을 때에 대해 증명하면, 두 사이클의 길이가 a / b라고 할 때, ..

(2020.11.24 01:27 - 모든 문제를 구현해서 풀이를 검증했으며, 일부 풀이를 고쳐 적었다.) (2020.11.23 01:32 - 모든 문제에 대한 풀이를 올렸다.) Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: Let Us Win ICPC WF (World Finals 진출 확정) KAIST: Everybody (World Finals 진출 매우 유력) 고려대학교: 1_Hoeaeng_2_Hawawang (World Finals 진출 예상) 숭실대학교: 181920 (World Finals 진출 가능성 있음) 성균관대학교: we need sleep 올해 서울 리저널은 관전자 입장에서 재밌게 볼 만한 요소가 아주 많은 대회였다. 그래서 관전..