총 5문제를 받았고 읽어본 문제가 2문제 있었다. 아는 문제 + 쉬운 문제 하나로 총 3문제를 풀었으며 나머지 두 문제는 풀이 구상을 마치고 구현은 시간 상의 이유로 하지 못했다. 시험 기간 + 과제 + 졸업논문을 맞아서 어쩔 수가 없게 되었다. 순서대로 풀이와 문제에 대한 생각을 기록해보았다.
Trous de loup (#)
판자가 없다면 간단한 투포인터 문제이다. 채울 구간을 결정한 뒤 판자를 덮는다고 생각하면 구간 내에서 가장 합이 큰 D개를 덮는 것이 최적이다. 누적합을 이용해 적절히 판자의 위치별 판자가 커버하는 양을 구해두면 구간의 최대값을 구하는 것이고 이는 덱을 이용해서 전체 시간복잡도 O(N)에 할 수 있다.
하지만 나는 처음에 생각을 편하게 하기 위해 파라메트릭으로 구간 길이를 결정하고 풀었고 이 때문에 로그가 붙어 상당히 느린 코드가 되었다. 결론적으로는 맞았지만 이번 선발고사에서도 Lag 문제를 불필요하게 DnC를 해서 로그를 하나 더 붙이고 맞았던 것처럼 생각해서 줄일 수 있는 부분은 줄여야 할 것 같다는 생각이 들었다. 뇌를 비우고 생각이 되는대로 풀다보니 이런 일이 자꾸 생기는 것 같다.
Dam (#)
19 국대교육 아침 셋에 있던 문제지만 풀이가 기억이 안 나서 다시 풀었다. 문제에서 요구하는 수온이라는 수치는 생각하기 불편하니 최대 열량? ((부피 * 온도)의 합, 간단히 열량으로 부르겠다.) 으로 풀고 답을 출력할 때 나누어 주어도 무방하다. 그럼 각 시점에서 "댐에 물을 x만큼 남길 때 남아있는 물의 최대 열량은 얼마인가?" 라는 식으로 DP를 할 수 있을 것이다. 물의 양을 x축, 열량을 y축으로 생각하면 곧바로 슬로프 트릭의 접근을 생각할 수 있다.
처음에는 y도의 물 L이 차있으면 (L, y)의 한 점만 찍혀 있을 것이다. 하나의 점은 하나의 상황을 나타내고 있다. 여기서 물을 빼는 행위는 물의 온도가 균일하게 혼합되어 있으므로 (0, 0)을 향해 직선으로 움직이는 꼴이 될 것이다. 그리고 새로운 물을 붓는 행위는 그래프 전체를 오른쪽 위로 평행 이동하고, x>L 부분을 날리는 꼴이 된다. 평행 이동과 각 점에서의 (0, 0)으로의 자취를 구하고, 그 upper envelope를 구하는 행위의 반복이므로 자명히 이 그래프는 볼록한 곡선이 된다. 이 곡선을 덱으로 관리하면 전체 시간 복잡도 O(N)에 짧은 코드로 문제를 해결할 수 있다. 열량으로의 변환 이후에는 간단한 변환 몇 번을 거쳐 풀 수 있지만 변환이 어려운 문제라고 생각한다.
애완 트리 (#)
작년 국대교육에서 UCPC를 쳤을 때 봤던 문제이다. 그때 나와 문홍윤이 이 문제를 같이 봤고 보자마자 동시에 풀이는 직감했다. 구현 정확도와 속도상 문홍윤이 치우기로 했고 꽤 깔끔하게 맞았던 것으로 기억한다. 풀이의 시작은 지름이 [S, E]에 속하는 트리의 개수를 지름이 E 이하인 트리의 개수에서 S-1 이하인 개수를 빼는 것으로 지름의 하한 조건을 없애는 것으로 시작한다. D[i][j]를 "정점 i를 루트로 하는 서브 트리중 i와 연결된 최장 경로의 길이가 j인 것의 개수"로 정의하면 O(N^3) 크기의 DP 테이블이 나온다. 이들을 위로 올려가며 단순히 채우기만 하면 되는데 여기에도 별다른 자료구조 없이 누적합을 잘 활용하여 단순하게 합쳐주면 시간 복잡도 또한 세제곱에 잘 풀린다.
내가 풀때는 솔브드 티어가 다이아 2였는데 너무 높다고 생각한다. 식을 세우고 최적화 하는 과정에서 그다지 어려운 아이디어가 없다고 생각한다. 처음 볼 때는 깊이 큰작 등의 테크닉이 들어가는 SciOi 방역 느낌의 문제라고 생각했지만 풀고 나니 조금 허무했다.
Cow optics (#)
우선 각 거울과 시작점, 끝점들로부터 4방향으로 선분들을 뻗어 점과 점 사이를 잇는 선분들 (또는 합쳐지지 않아 반직선인 상태) 로 적당히 합쳐준다. 여기서 시작점으로부터 나가는 광선의 경로에 해당하는 선분들을 체크하고, 도착점과 연결되어 있는 모든 선분을 체크해준다. 이렇게 해놓고 나면 거울을 놓아 두 경로를 합쳐줄 수 있는 위치는 시작점과 연결된 선분과 도착점과 연결된 선분의 교점들이다. 한가지 문제점은 원점으로 돌아가서는 안된다는 조건인데, 이는 적당한 관찰을 통해 시작점과 도착점을 포함하는 어떤 경로에서 그 둘 사이를 제외한 너머의 선분들은 도착점 쪽의 선분으로 체크하지 않으면 된다는 사실을 알 수 있다. 둘을 포함하는 사이클이 있다면 사이클의 간선은 모두 사용 불가능하다.
(xxxxx A ------ B xxxxx 와 같은 꼴.)
선분의 교차점은 스위핑으로 간단히 해결 된다. 말은 쉽지만 구현이 굉장히 길어질 것으로 보인다. 스위핑도 두 번해야 하고 선분들을 따라가며 체크하는 단순 코딩이 짧을 것 같지는 않다. 좋은 구현 연습 문제인 것 같다.
Highway Modernization (#)
풀이는 매우 단순하다. 각 간선을 잘랐을 때 나누어지는 양쪽 트리의 지름을 알면 최대화에서는 길이의 합 + 1이 답이 될 것이고 최소화에서는 지름의 중심끼리 이으면 답이 될 것이다. 모든 간선 길이는 1이기 때문에 단순히 이때의 지름의 중심과 가장 먼 점의 거리는 ceil(지름/2)가 될 것이다. 각 간선을 자를 때의 답을 구하는 것은 DP로 어렵지 않게 가능하다. 답의 역추적 또한 어느 간선을 자를 때 답이 나오는 지를 알고 있다면 O(N)에 끝점이나 중심을 찾는 것은 어렵지 않다. 이 문제도 마찬가지로 구현은 굉장히 길어질 것 같다. 역추적 부분이 매우 귀찮을 것으로 보인다.