이번 주는 총 5문제를 받아 모두 풀었다. 모두 적당한 난이도에 생각을 충분히 해볼 수 있는 문제들이었다고 생각한다. 밑의 풀이는 푼 순서대로 작성하였다.
최고인 대장장이 토르비욘 (#)
먼저 관찰할 수 있는 사실은 직사각형 중에 밑변의 길이가 같은 것이 없다면 그냥 순서대로 정렬해서 쌓으면 조건을 만족시킬 수 있다는 사실이다. 따라서 문제를 "정수 페어가 N개 들어올 때 중복되지 않게 각 페어에서 하나씩 숫자를 뽑아 그 합을 최소화하는 문제"로 변형할 수 있다. 여기서 정수 페어를 간선으로 생각하고 각 수를 정점으로 하여 그래프를 생각해보자. 이제 각 간선별로 양 끝점을 하나씩 배정해 주는 문제가 되는데, 컴포넌트 별로 분리해서 생각해도 무방하다. 만약 컴포넌트에 간선이 정점보다 많다면 이는 배정 불가능하다. 둘의 수가 같다면 functional graph가 되고 그냥 모든 정점을 뽑으면 된다. 남은 경우는 트리 밖에 없고 둘의 차이가 한 개이므로 그냥 가장 큰 정점 하나를 버리면 된다. 결론적으로는 Union-find 하나만 들고 적당히 풀 수 있는 문제가 되었다. 그냥 DFS를 돌아도 되고 적절히 구현하면 된다. 코딩은 매우 간결하다.
상금 분배 (#)
우선 수를 오름차순으로 정렬하고 생각하자. 첫 번째 관찰은 P3을 고정하면 P4~7은 그냥 그 앞에 딱 붙여 연속으로 4개를 뽑는 것이 최적이라는 사실이다. 합의 최대화에도, 부등식의 성립에도 유리하다. 이제 N개의 각 P3에 대해 P1, P2쌍을 최적으로 고르는 방법을 생각해보자. 우선 P3~7을 결정한 시점에서 P2의 값에는 상한선이 걸린다. 여기서 케이스를 두가지로 분리할 것이다.
(1) P1을 P2의 상한선보다 크게 잡을때 : P1이 P2의 상한선보다 크다면 만족시킬 남은 조건은 P1<P2+P3 밖에 없다. 이 상황에서는 P1을 어떻게 잡더라도 P2는 무조건 상한에 딱 맞춰 최대한 크게 잡는게 이득임을 알 수 있다. 따라서 P2를 바로 고정해주고, 그에 맞춰 P1의 최대값을 찾아 더해주면 된다.
(2) P1이 P2의 상한 이하가 될 때 : 여기서 맞춰야 할 조건은 P1>P2와 P1<P2+P3의 두 식이다. 여기서도 역시 P1이 정해졌다면 P2는 클수록 좋기 때문에 P1과 P2를 바로 인접하게 고르면 된다. 이제 P1 - P2 = A_i - A_{i-1} < P3를 만족하는 i중 가장 큰 i를 범위 내에서 빠르게 찾으면 되고, 나는 세그먼트 트리에서 이분 탐색을 했다.
따라서 각 케이스가 로그에 처리 되므로 총 시간 O(N log N)에 풀린다. 세그 이분탐색의 좋은 활용 문제인 것 같다. 굳이 세그 이분 탐색이 아니라도 머리를 쓰면 간단하고 짧은 해법이 있을 것 같기는 하다.
Hotel (#)
우선 처음 봤을 때 생각한 풀이는 소각로 문제처럼 셋으로 구간을 적절히 관리하는 방법이었다. 하지만 소각로 때와 달리 코딩이 정말 복잡해 보였고 N, M 50000의 제한은 루트가 충분히 돌아갈 것 처럼 보였다. 따라서 그냥 루트 연습도 할겸 버킷질을 해서 풀기로 했다. B 크기의 버킷으로 적절히 나누고, 각 버킷의 왼쪽에서 연속한 (사용 가능한) 최대 길이, 오른쪽에서 연속한 최대 길이, 내부의 최대 연속 길이를 저장한다. 이를 저장하면 답을 계산하는 것은 버킷 단위로 건너뛰며 여러 버킷에 걸쳐있는 경우와 아닌 경우를 따져 O(N/B + B)정도의 시간에 해결 가능하다. 값을 칠하는 연산도 레이지와 같은 느낌으로 해주면 O(N/B) 시간에 체크를 해주고 칠하는 구간의 양 끝점이 속하는 버킷에 대해서만 O(B)시간에 위의 값들을 갱신해 주면 된다. 따라서 총 시간 복잡도 O(Q(N/B + B))로 해결된다. 상수가 별로 크지 않아서 제출해봤더니 로그와 전혀 차이 없는 (오히려 꽤 빠른?) 시간에 풀렸다. 쉽고 짧게 짤 수 있다는 점에서 연습을 많이 해두면 루트는 괜찮은 선택지인 것 같다.
투명 악어 (#)
먼저 각 칸의 숫자가 20미만이라는 점에서 해당 칸에 있는 앞발과 뒷발의 총 개수를 정확하게 알 수 있다. 이제 앞발과 뒷발을 적절히 매칭해주면 된다. 만약 같은 칸에 있는 발을 매칭할 수 있다면 연결끼리 교차하지 않도록 순서대로 매칭하는 것이 최적임을 관찰할 수 있다. 그러나 이 조건 때문에 간단한 그리디는 성립하지 않는다. 여기서 DP 풀이를 떠올려보자. D[i][x][y] 를 '현재 i번 위치까지의 발들을 매칭한 결과, i+1칸 쪽으로 넘어가는 앞발이 x개, 뒷발이 y개인 최소의 길이 합'으로 정의해보자. 단순히 생각해보면 N^3짜리 테이블이 나와서 쉽지 않다. 여기서 한가지 생각을 해보면 어떤 시점에서도 두 종류의 발이 모두 한 칸에 있을 수 있는 발의 최대 개수를 넘지는 않을 것이라는 생각을 해볼 수 있다. 문제가 생긴 이유가 같은 칸의 발쌍을 매칭하지 못하기 때문이라는 점에서 떠올릴 수 있다. 둘 다 5개를 넘어가는 경우를 생각하면 교차를 적당히 풀어서 값이 줄어들게 할 수 있다. 마지막으로 x와 y값은 독립이 아니라 1~i 까지의 총 발 개수내에서 매칭된 결과이기 때문에 각각 가질 수 있는 값의 범위가 상수개로 제한되면 하나의 i에서 테이블의 크기도 상수가 된다. 따라서 O(N)에 문제를 해결할 수 있게 된다. 나는 테이블을 저장하는 방식을 만들기가 귀찮아서 하나의 D[i]를 map<pair, int>로 적당히 처리해서 로그가 하나 붙었다.
J-th number (#)
자료구조 + 쿼리 테크닉 연습 문제다. 우선 '특정 구간 안에 있는 v이하의 값의 개수'를 빠르게 알 수 있다면 각 쿼리에서 이분 탐색을 하면 k번째 수를 알아낼 수 있다. 이제 저 값을 빠르게 계산하는 방법은 값의 크기를 시간 축으로 옮기는 것이다. 값의 크기 순서대로 업데이트 쿼리들을 더하면서 적절한 시점에 구간의 합을 구하는 것이다. 여기서 여러 개의 쿼리를 해결하는 방법이 두 가지로 갈린다. 하나는 업데이트를 PST로 만들어서 각 쿼리마다 이분 탐색을 따로 진행하는 방법이다. 다른 방법은 쿼리에 병렬 이분탐색을 적용해 단순 레이지 세그를 짜 시간축을 그대로 반영하고 되돌리지 않는 것이다. 나는 후자를 짜서 맞았고, 시간이 꽤 오래 걸렸다. 10초 제한에 9초가 걸렸으니 아슬아슬 했던 것 같다. 아마 다이나믹 세그를 짜서 상수가 꽤 컸기 때문인 것으로 보인다.