오랜만의 문제 풀이이다.KSAAC 2023 summer에 출제된 테마파크 문제이다. s의 서브트리를 기준으로, 어떤 두 간선도 조상-후손 관계에 있지 않은 간선 집합들을 관리해두면, s와 부모를 잇는 간선과 비교해서 써먹을 수 있을 것 같다. s와 부모를 잇는 간선에서의 비용을 ws라고 하자. 당연히 s≥1일 때만 정의할 수 있다. 서브트리 속 여러 정보를 효율적으로 관리하는 것은 보통 스몰투라지 기법이 잘 먹힌다. 풀이를 조금 더 구체화해보자. 우선, 각 정점은 자신보다 윗쪽에 있는 간선들과 교류가 생기므로 일반적으로 트리 문제를 풀 때 s의 서브트리에 정점 s를 포함하는 것과는 달리, 정점 s는 제거하는 식으로 값들을 정의하자. ℓs:= 정점 집합 $s^..
대회 문제들은 여기서 확인하실 수 있습니다. 문제별로 제가 기여한 것들과 짧은 후기를 정리해보겠습니다. 전체적인 제안 검수를 딱 하려고 보니까 문제별로 tests가 150개를 넘어가던 걸로 기억합니다. 가뜩이나 Arena가 적용되어서 참가자 수가 많아질 것 같은데 tests가 이대로 많으면 안 될 것 같다고 줄여달라고 제안을 드렸습니다. 좀 늦게 제안했는데, 왜 그 전까지는 아무도 말을 안 꺼냈는지는 잘 모르겠네요.. 😅 또, 그래프 문제들의 조건에서 "1≤i,j≤N인 모든 i, j에 대해서 i번 구역에서 j번 구역으로 가능 경로가 항상 존재"를 " 1≤i<j≤N인 모든 i, j에 대해서 i번 구역과 j번 구역을 연결하는 경로가 존재"로..