ZOAC 2019 후기 및 풀이
안녕하세요 hellogaon입니다.2019년 12월 28일, 작년에 이어 한양대학교 에리카 알고리즘 학회 '영과일'의 내부 대회Zero One Algorithm Contest 2019(이하 ZOAC 2019)가 개최되었습니다. 대회가 열리기 한 달 전, 대회 개최 조건이 변경되어 3명 이상의 검수진이 필요하였고 자칫하면 대회가 열리지 못할 뻔도 하였으나 영과일 회장님의 대회를 개최하겠다는 열정에 감동하여검수진을 구할 수 있었다는 후문이 있습니다. 출제자로는 저와 재현이(TheKinGoD)와 병서(bsyun0571)가 참여하였고 정말 훌륭하신 cheetose님, functionx님, h0ngjun7님, jh05013님, oree2113님, rdd6584님께서검수진으로 참여해주셔서 더욱 높은 퀄리티의 대회를..
3176번: 도로 네트워크 - LCA 간선에 가중치가 있는 트리가 주어질 때 정점 u에서 정점 v까지의 경로의 간선들 중가장 작은 가중치, 가장 큰 가중치를 출력하는 문제이다. 100,000개의 쿼리를 처리해야하기에 효율적인 방법이 필요한데경로가 유일하다는 것을 이용하여 LCA를 이용해보자u, v의 경로는 u - LCA(u,v) - v 로 이루어져 있기 때문이다.그렇다면 LCA를 구하면서 가장 작은 가중치, 가장 큰 가중치를 구할 수 있을까?LCA에서는 정점의 2^k번째 부모를 저장해놓는다.즉 한 정점의 2^(k+1)번째 부모는 그 정점의 2^k번째 부모의 2^k번째 부모와 같다를 이용하였다.이와 비슷하게 한 정점의 2^(k+1)번째 부모까지의 가장 작은 가중치는min(그 정점의 2^k번째 부모까지의 가..