POI 2010/2011 (~Platinum) 풀이 및 후기

solved.ac 기준 플래티넘 아래쪽 문제들을 돌았다. POI를 쫙 돌겠다는 생각이 있긴 했는데, 연속적인 연도를 돌 생각은 딱히 없었지만 우연히 후기가 올라간 게 3년 연속이 되었다. 그리고 슬슬 unrated인 문제가 보이긴 하는데... 일단 나중에 건드릴 예정.

Lollipop

이 시리즈를 만들면서 푼 문제는 아니고, 예전에 풀었었던 문제이다. 그런데 이번 셋에서는 제일 재밌는 문제인 듯.

문제의 핵심은 내가 \([l, r]\)과 \([l, r+1]\)로 자른 사탕을 생각했을 때, 값의 차이가 커 봤자 \(2\)라는 점이다. 그러면 만약 \(l-1\)번째 사탕이 값이 1인 사탕이라고 하자. 그러면 \([l, x]\) 혹은 \([l-1, x]\) 중 하나를 골라서, \([l-1, n]\) 길이 이하의 모든 길이를 다 만들어낼 수 있다. 따라서 가장 왼쪽, 가장 오른쪽 \(1\) 사탕의 위치로 처리하면 된다.

Lightning Conductor

요즘에는 웰노운이지만, 이상한 곳으로 생각이 빠져서 못 풀었다. \(i\)에 conductor를 달 때, \(j\)를 커버하기 위한 높이 \(p_i\)를 \(f(i, j)\)로 정의하자. 통상적으로 내가 고려하는 어떤 '비용'이 2변수 함수로 주어진다면 늘 단조성과 같은 성질을 찾아보려고 해야 하는 것 같다. 우선 \(i < j\)인 경우만 고려하자. \(i_1 < i_2\)에 대해, \(f(i_1, j)\)가 최대인 \(j_1\)과 \(f(i_2, j)\)가 최대인 \(j_2\)가 \(j_1 \leq j_2\)를 만족한다. 그러므로 DnC optimization을 사용하면 ok. \(i < j\)인 경우만 고려했으니 빌딩 순서를 거꾸로 놓고 같은 로직을 한 번 더 써주면 ok. 처음엔 \(O(n\sqrt{n})\)으로 뚫어보려고 갖은 시도를 했는데 실패했다. 근데 나중에 보니까 실제로 뚫린다고 합니다..?

결국 \(\sqrt{x}\) 함수의 볼록성으로 인해서 단조성이 얻어지고, 단조성으로 optimization을 하는 그런 문제였다. 이런 문제들은 보통 비용에 관여하는 변수가 2개이거나 혹은 잘 2개로 줄이는 방법을 거쳐서 푸는 경우가 대부분인 것 같다. 이 문제가 재밌었던 점은 dp식을 세웠을 때 뭐 비용이 monge array를 만족해서 단조성이 있다, 이런 식으로 표현되는 경우가 많은데 이 문제는 naive하게 단조성이 존재하는 경우였다는 것이다.

그렇지만 놀랍게도 이 문제의 정해는 \(O(n)\)이다. 위에서의 풀이랑 별로 다를 게 없긴 하지만, 실제로 실행시간을 보니 코드가 유의미하게 빨라지는 풀이인 것 같아서 소개해보고자 한다. 다음 두 개의 관찰을 이용한다.

관찰 1. \(M\) 위치에서 최대 높이 \(h[M] = H\)를 가진다고 하자. 이 때 \(H - \lceil \sqrt{n} \rceil\)보다 높이가 작은 위치는 다른 건물 입장에서 \(p\)를 계산할 떄 고려하지 않아도 된다. 증명은 직관적이니 pass.

관찰 2. \(i < j_1 < j_2\)일 때 \(h_{j_1} < h_{j_2}\)라면 \(j_1\)은 딱히 고려할 필요가 없다.

관찰 2는 오른쪽에서부터 왼쪽으로 빌딩을 높이에 대한 단조성을 가지는 스택에 넣고 관리할 수 있지 않을까라는 생각을 하게 해 준다. 그러면 관찰 1까지 적용할 경우 우리가 궁금한 빌딩은 해봤자 최대 \(\lceil \sqrt{n} \rceil + 1\)개이다. 그러면 한 번 순회를 마치고 스택에 남은 원소들로만 dnc opt 풀이처럼 최대가 되는 위치의 단조성을 이용하는 아이디어를 떠올릴 수 있다. 위에서는 빌딩을 고정하고 최댓값을 주는 위치를 찾았지만, 최댓값을 주는 위치를 고정하고 그에 의존하는 빌딩의 위치를 봐도 단조성은 여전히 남아있다. 스택에서 인접한 두 원소 \(1 \leq a < b \leq n\)이 있을 때, \(cross(a, b)\)를 \(a\) 빌딩이 \(b\) 빌딩보다 '지배력'이 높은 최대의 위치를 나타내는 함수라고 하자. CHT에서 직선들의 교점을 관리하는 것과 정확히 같은 원리로, 이 문제에서도 스택에 원소들을 넣을 때 \(cross\) 함수의 값의 단조성이 유지되게 관리를 해주면 된다. 앞에서 높이에 대한 단조성은 편의상 언급한 것이고, 아마 \(cross\) 함수를 계산했으면 자연스럽게 스택에 남은 원소들이 높이 순서대로 정렬될 수밖에 없긴 하다. \(cross\) 함수는 이분 탐색으로 \(O(logn)\)에 원하는 값을 알아낼 수 있으므로, 전체 시간 복잡도는 \(O(n+\sqrt{n}logn) = O(n)\)이다.

Shift

우선 정렬이 가능한지에 대한 판별부터가 아주 자명하지는 않다. 일반적으로 정렬과 관련된 불변량은 inversion이니, 각 operation이 inversion을 어떻게 변화시키는지 관찰해보자. b 행동은 inversion을 정확히 짝수만큼만 바꾼다. 같은 원리로 a 행동은 \(n\)이 홀수일 때는 짝수만 바꾸며, \(n\)이 짝수일 때는 홀수만큼도 바꿀 수 있다.

또한 a 행동은 전체 배열을 환형 배열로 볼 수 있게 해 준다. 즉 b 행동을 어느 위치에서도 연속한 3개의 원소를 회전시키는 연산으로 볼 수 있다. 그러므로 \(2\)부터 시작하여 \(n\)까지, \(i\)를 \(i-1\) 바로 오른쪽으로 이동시키는 방법을 반복했을 때 정렬이 되면 ok이고, 아니면 불가능한 것이다. b 행동으로 수를 왼쪽으로 2칸씩 이동시킨다고 생각하면 되고, 1칸만 움직이고 싶으면 \(i\)를 b 행동의 두 번째 위치에 놓으면 된다.

\(n < 3\)일 때는 예외처리를 해주는 게 편한 것 같고, b 행동이 최소 3개의 수를 건드린다는 점 때문에 \(n-3\)까지 정렬하고 나면 로직이 약간 애매하다고 볼 수도 있는데, inversion 개수가 올바른 경우 무조건 \(n-2, n-1, n\)은 이 상태로 순환하는 3가지 경우밖에 안 되기 때문에 잘 정렬된다. 편한 방식대로 정렬하면 될 듯하다.

Difference

이 문제는 첫 생각을 잘못 시작하면 말리기 쉬운 문제였을 것 같다. 핵심은 최대로 등장하는 알파벳, 최소로 등장하는 알파벳의 쌍을 가정하고 문제를 풀려고 시도했을 때, \(26 \times 26 = 676\)번만 생각하면 된다는 뜻이다. 그리고 알파벳을 고정하고 봤을 때는 prefix sum을 이용하여 \(O(n)\)에 문제를 해결할 수 있다. 예를 들어 \(a\)가 가장 많이, \(b\)가 가장 적게 사용된 문자열이라고 생각할 경우, \(a\)를 \(1\)로 \(b\)를 \(-1\)로 두고 구간 연속 최대 합을 구하면 된다.

그리고 각각의 시간이 \(O(n)\) 걸린다고 서술을 했으나, 사실 \(676\)번 도는 동안 내가 보게 되는 문자열 길이의 총합은 \(26n\) 정도이다. 가장 많이 나타나는 문자열을 고정했을 때, 나머지 문자들은 다 합쳐서 많아야 \(n\)개가 있는 것이므로 \(a\)가 \(25\)번 나타날 동안 나머지 문자들이 \(n\)개 나오기 때문.

Garbage

\(s \neq t\)인 모든 간선들을 모으면, edge-disjoint simple cycle decomposition이 가능한지 묻는 문제로 바뀐다. 즉 euler circuit에 관한 문제이고... 그러한 간선들만 모은 그래프를 만들었을 때 모든 정점의 차수가 짝수인지 아닌지로 불가능성 판정을 우선 할 수 있다.

가능하다고 하면 내가 찾을 수 있는 사이클을 전부 찾으면 된다. dfs를 돌면서 사이클을 찾고, 그 사이클을 그래프에서 지워주는 과정을 반복하자. 이 문제의 어려운 점 중 하나는 어떻게 간선을 그래프의 adjacency list에서 제거할 것이냐 하는 문제일 듯하다. 방법은 내가 지우고 싶은 간선 \((i, j)\)가 있을 때, adj[i]에서 \(j\)를 list의 맨 끝에 있는 원소와 swap하고, adj[j] 입장에서도 똑같이 해준다. pop_back()은 \(O(1)\) 시간에 가능한 연산이기 때문에 ok. 즉 이걸 위해서는 Edge라는 struct를 만들고, 각 간선의 양 끝 점과 그 간선이 끝 점의 adjacency list에서 몇 번째 칸에 현재 저장되어 있는지 정보를 관리하고 있으면 될 것이다.

그 외에도 다양한 방법이 있을 수 있는데, linked list를 쓰는 게 사실 더 쉽지 않았을까라는 생각이 들긴 한다. 그리고 아예 euler circuit을 찾아버린 다음에 simple cycle로 쪼개서 출력해주는 방법도 ok일 듯한데, 내가 아는 euler circuit의 구현은 종만북 버전밖에 없고 이 경우 adjacency matrix를 쓴다. 그러므로 위에 설명한 두 방법 중 하나가 최선일 듯.

Temperature

국밥 같이 자주 등장하는 유형...이라고 생각한다. 만약 특정 구간에서 non-dropping temperature가 가능한지 판별하고 싶다고 하자. 시작점을 고정했을 때, 시작 날의 온도는 그 날의 가능한 온도 범위 중 최소라고 가정하는 것이 항상 이득이다. 그리고 계속해서 다음 날을 봤을 때도, 최대한 온도를 상승시키지 않는 것이 이득이다. 그렇게 하다 보면 상당히 많은 날에 greedy하게 관리하고 있는 온도는 그 날의 온도 범위 중 최소인 경우라고 볼 수 있다. 그러므로 이걸 계산하다 보면 동일한 상태에 자주 접근하게 될 것이고, \(dp[i]\)라는 걸 \(i\)의 최소 온도에서 시작하여 어디까지 non-dropping temperature를 유지할 수 있는지로 정의하고 싶어진다.

전이식을 계산하기 위해 필요한 정보 중 하나는, 날짜 \(x\)에서 온도 \(t\)인 상태가 되었을 때 \(x+1\)일차의 최소 온도가 \(t\)보다 작아서 온도를 유지할 수 있는 상태를 잘 관리하는 것이 필요하다. 왜냐하면 이 상태가 언제 끝나는지를 naive하게 찾으려고 하면 모든 dp 테이블을 채우는데 \(O(n^2)\) 시간이 소요될 수 있기 때문이다. 그렇기 때문에 나는 \(l\)부터 \(r\) 날짜들 중 나타나는 날짜 범위의 최댓값들의 최소, 최솟값들의 최대를 관리하는 sparse table을 만들어서 \(t\)로 유지될 수 있는 시간을 계산하는 과정을 \(O(logn)\)로 줄였다.

이러한 방식은 놀랍게도 메모리 제한에 걸리는데, sparse table을 만들면 200MB 정도가 필요하기 때문에 급하게 해결책으로 sparse의 간격을 \(2^k\)꼴이 아니라 \(4^k\)꼴로 만들어서 메모리는 절반으로 줄이는 대신 계산을 2배 늘렸다. POI 풀 때마다 느끼는 건데, 시간 제한도 그렇고 메모리 제한도 그렇고 꽤나 상남자식 제한을 주는 것 같다. Garbage 문제에서도 그랬지만 정점/간선이 다 \(10^6\)개씩 주어지는데 시간제한은 1초에 메모리제한은 128MB라는 요즘 기준으로는 매우 뺵빽한 기준을 제시한다. 좀 더 옛날 POI로 가면 32MB 메모리 제한이 보통인 것 같은데, 그런 건 아마 32-bit architecture 쓰던 시절이 아닌가라는 추정.

다만 이 풀이는 정해로부터 매우 멀리 떨어져 있는 풀이이다. 정해가 무엇인지 언급하고 넘어간다. \(a < c \leq d < b\)에 대해, \([a, b]\)가 가능한 구간이라면 \([c, d]\)도 항상 가능한 구간이라는 성질이 있다는 걸 주목하자. 그러면 two pointer처럼 \(i\)에서 시작하여 최대의 가능한 오른쪽 구간을 찾은 다음, 최대에 도달한 이후 \(i\)를 \(1\) 증가시켜서 모든 값을 고려하는 것이다. 가능한지 항상 판별하고 있기 위해서는, 사실 한 가지 조건만 확인하면 된다: \(\max(x_i, x_{i+1}, \ldots, x_j) \leq y_j\). 이러면 \(\max\) 값을 segment tree 등으로 관리해주면 ok. 혹은 two pointer처럼 구간이 움직인다는 조건 때문에 queue로 \(\max\) 값을 관리하고 있을 수도 있다. 이러면 \(O(n)\)에 동작하는 풀이까지도 얻을 수 있다.

Party

이 문제는 내가 PS를 시작한 지 몇 달 되지도 않았을 때 추천받았던 문제 중 하나인지, 여태껏 까먹고 있다가 이번 기회에 다시 풀어봤다. 문제는 제대로 푸는 방법을 몰라서 결국 이상한 방법으로 뚫었다는 점이다. 또 다시 POI스러운 특이한 조건을 덧붙인 NP-hard 문제이다. 이 문제의 정해는 매우 간단하다. 둘 사이에 간선이 없는 정점 쌍을 아무거나 하나 고르자. 그 정점을 그래프에서 동시에 제거한다. 그러면 원래의 그래프에서 \(2k\) 크기의 clique이 있었을 텐데 이번에 제거한 두 정점 중 최소 한 개는 그 clique의 원소가 아니어야 한다. 그렇다면 이 과정은 아무리 많아야 \(k\)번 반복되고, 남은 그래프 전체가 clique이 되었을 때 최소 \(k\)개의 정점이 남아있는 것이 보장된다.

난 이 풀이를 못 떠올렸고, 적당히 randomized algorithm이 잘 통할 것처럼 생겼길래 생각을 해 봤다. 최종적으로 출력으로 내놓을 clique을 점점 incremental하게 만들어나갈 것이다. 어떤 시점에 clique에 포함되지 않은 정점들 중 하나를 랜덤하게 선택한다. 만약 그 정점이 clique과 전부 연결되어 있다면, 이건 높은 확률로 그래프에 원래 존재하는 \(2k\) 크기의 clique의 원소라고 판단할 수 있겠다. 다만 아주 운 나쁘게 아닐 수도 있긴 하다. 그러므로 일종의 recovery가 가능한 전략을 짜야 한다. 아까와는 반대로 clique의 어떤 정점과 연결되지 않은 정점이 선택되었다고 하자. 이러면 연결되지 않은 정점과 1대1로 막고라(?)를 시킨다. \(50\)% 확률로 \(0\) 아니면 \(1\)을 뽑고, \(0\)이 나오면 현재 고려하는 정점을 그만 보고, \(1\)이 나오면 clique에서 정점을 제거한다. 이렇게 해서 모든 간선이 없는 clique의 원소들이 제거되면 그제서야 처음에 고른 정점을 clique에 넣는다.

사실 이 전략이 나름 의미가 있기는 하다. clique의 크기가 작으면 원래 그래프에서 \(2k\) clique에 속하지 않는 정점들이 우연히 연결되어 있을 확률이 높긴 하지만, 그만큼 recovery 전략에서 그러한 정점을 없애게 될 확률도 높다. 그러므로 여러 번 시행을 하다 보면 평균적으로 원래 그래프에서 큰 clique을 어느 정도 흉내낼 수 있게 된다는 논리이다. 너무 랜덤하게 정점이 뽑혀서 시간 안에 테스트를 못 하게 될 가능성을 고려하여, round라는 개념을 생각한다. 하나의 round에서는 현재 clique에 속하지 않은 정점을 한 번씩은 전부 보되 그 안에서 순서를 랜덤하게 뽑고, clique에서 중간에 방출된 정점들과 clique 안에 들어가지 못한 정점들을 모아서 새로운 round를 시작하면 된다. 이렇게 구현을 해야 거의 \(1\)초를 다 써서 AC를 받았기 떄문에, 꽤 유효했던 듯하다.

Sticks

삼각형의 가장 긴 변이 될 막대를 고정하고 생각하자. 그 길이 이하인 막대 중 가장 긴 변으로 고정한 막대의 색깔과 다른 색깔을 가지면서 가능한 최대의 길이인 두 막대를 고르는 것이 항상 이득이다. 따라서 막대를 색깔 구분 없이 길이 순서대로 전부 정렬하고, 하나씩 보면서 현재까지 본 가장 긴 막대기 3개의 길이와 색깔을 저장한다. 이 때 3개의 색깔은 전부 다른 상태를 유지하도록 관리하면 ok.

Programming Contest

꽤 educational한 문제인 것 같다. 보통 이런 문제는 flow로 모델링을 해야 한다. 왜냐면 subproblem을 찾기가 매우 힘들고, 그래프로 모델링되기 매우 좋은 문제이기 때문이다. 원하는 것은 최소의 패널티이므로 MCMF를 생각해볼 수 있다. 사람을 노드로 만들고, 그 노드는 source로부터 나오는 비용 \(0\), 용량 \(m\)인 간선과 연결해둔다. (즉 용량은 사실상 무한대) 또한 각 노드들에 노드를 하나씩 더 달아둔다. 두 노드 사이에는 비용이 \(r\)인 간선, \(2r\)인 간선, ...이 계속해서 있고, 용량은 모두 \(1\)로 설정한다. 이러면 \(a\)문제를 풀었을 때 얻는 패널티를 잘 시뮬레이션할 수 있다. 그리고 문제에 해당하는 노드들을 만들어서, \(a\)가 \(b\)를 풀 수 있으면 \(a\)와 연결된 노드, 그리고 \(b\)에 대응되는 노드를 비용 \(0\), 용량 \(1\)인 간선으로 연결한다. 모든 문제와 sink를 용량 \(1\), 비용은 \(0\)인 간선으로 연결하면 ok. 그래프를 구성할 때 \(a\)가 \(b\)를 풀 수 있다는 정보를 저장해둔 \(2\)차원 배열에서 참조해야 하는 차원을 잘못 설정해서 좀 고생했다.

그 외에도 매우 다양한 풀이가 있는 문제로 보인다. 두 풀이 모두 핵심은 사람들에게 배정된 task의 개수가 고르게 배정될 수록 이득이라는 점을 이용한다. 첫 번째 풀이는 이분 매칭을 \(\lfloor \frac{t}{r} \rfloor\)번 시행하는 것이다. 이러면 각 매칭에서 사람들이 최대한 고르게 1개의 task를 배정받게 되고, 이를 할 수 있는 만큼 시행하면 된다. 두 번째 풀이는 ford-fulkerson처럼 유량을 하나씩 일일이 더 흘려보내는 것을 시도하는 풀이이다. 현재 task를 가장 적게 배분받은 사람에게 task를 1개 더 배정할 수 있는지 판별하고, 안 되면 후보군에서 제외하자. 이를 더 이상 유량을 흘려보낼 수 없을 때까지 반복하면 ok.

두 풀이 모두 정당성을 증명할 필요가 있긴 한데, 첫 번째 풀이의 경우 현재 흐르는 유량이 \(f\)일 때, \(f\)가 흐를 때 비용이 최적인 상황과 비교하면 항상 최적이 아닌 상태에서 최적으로 가는 cost-improving alternating path가 있음을 보이면 된다. 두 번째 풀이는 플로우 자체의 정당성과 거의 유사하므로 직관적으로 이해할 수 있을 것이다.