주간 PS 리뷰
국대교육 멘토링 때 잠시 사용한 이후 버려진 블로그를 활용하기 위해 앞으로 매주 하나씩 내가 한 주간 풀었던 문제들의 리뷰를 작성할 계획이다. 내가 푼 문제를 정리하는 차원에서도 좋을 것 같고 뭔가 기록을 남긴다는 의미에서 세운 계획이다. 또, PS를 공부하는 사람들에게도 여러 문제들에 대해 참고할 자료를 남기면 좋을 것 같다는 생각이다. 설명 능력도 부족하고 아는 것도 많지는 않지만 노력해보려고 한다. 노력하다보면 언젠가는 구사과 블로그처럼 대단한 블로그가 될 수도 있지 않을까?
리뷰하는 문제는 그 주에 내가 푼 문제들이고, 그 중에서도 나름 의미가 있는 문제들을 추려서 작성할 계획이다. 글이 길어지거나 중요한 주제라고 생각되는 문제들은 리뷰에서 언급만 하고 따로 글을 쓸 수도 있을 것 같다. 코드포스를 치거나 대회에 나간다거나 하면 간단하게 대회 문제들도 볼 계획이다.
Arranging Tickets
JOISC (JOI spring camp) 2017 day2
풀이가 길고 복잡하므로 간단한 설명만 하고 나중에 따로 글을 쓰려고 한다. (첫 문제부터...)
문제는 이렇다. 원 위의 구간들이 여러 개 주어질 때 각 구간을 여집합으로 뒤집는 연산을 시행할 수 있다. 잘 시행했을 때 원 위의 단위 구간들 중 겹쳐있는 구간 수의 최댓값을 최소화 하는 것이다. 일단 최댓값의 최소화가 목적이므로 파라메트릭을 박고 시작하도록 하자. 원을 다루는 것은 곤란하므로 1번을 기준으로 잘라 원을 펼치도록 하자. 이때 구간들은 모두 잘리지 않고 온전히 들어오도록 잘 뒤집어주자. 이 상태를 초기상태라고 두고, 뒤집을 구간들을 잘 선택해 주는 것으로 문제를 변환할 수 있다. 여기서 아주 중요한 관찰 하나로 풀이를 시작할 수 있다. 최적해에서 뒤집어지는 구간들은 모두 공통된 교집합을 가지고 있다는 점이다. 교집합이 없는 구간 두 개가 모두 뒤집어질 경우에 대해 생각해보면 알 수 있다. 이제 1~N까지의 단위 구간에 대해 각 구간 t가 교집합에 들어가고, n개의 구간을 뒤집어, 겹친 구간의 수를 m개 이하로 만들어 보자. t, n, m이 모두 결정되면 O(N lg N)에 가능 여부를 판별할 수 있다. m은 파라메트릭으로 결정하므로 총 시간은 O(N^3 lg^2 N)이 된다. 이후 O(N lg^2 N)으로의 최적화는 수식을 통해 열심히 증명해서 t와 n의 후보가 각각 2개씩 밖에 없다는 사실을 보이면 된다. 이 부분은 기회가 된다면 추후 자세히 설명하도록 하겠다.
Valleys
USACO 2019 US Open Contest Platinum
우선 valley의 조건 중 '주변 셀들보다 낮을 것' 에 해당하는 조건은 격자에서 가장 낮은 칸부터 색칠하면서 색칠할 때마다 그 칸을 포함하는 region을 봐주면 어렵지 않게 해결할 수 있다. 높이가 모두 distinct하다는 조건도 있으니 헷갈릴 것도 없다. 핵심이 되는 부분은 어떤 region이 holey한지 판단하는 것이다. flood-fill 외에는 별로 방법이 없어 보이지만, 그냥 사용하기에는 시간 상 개선의 여지가 없다. 여기서 한 가지 아이디어가 필요한데, 바로 격자는 평면그래프라는 사실이다. 그리고 평면그래프에서는 면과 관련된 V-E+F=2라는 멋진 등식이 성립한다. 각 칸을 정점, 인접한 변을 간선으로 두면 면의 개수는 곧 구멍의 개수라는 사실을 알 수 있다. 주의할 점은 여기서 말하는 구멍에는 그래프의 외부와, 한 꼭지점을 공유하는 4칸이 만드는 사각형도 포함되어 있다는 점이다. 이 면들은 문제 조건의 holey함에는 포함되지 않는 면들로 따로 세서 빼주어야 한다. 결론적으로 낮은 칸부터 색칠하면서 유니온 파인드 등으로 region과 V, E, F값을 잘 합쳐주면서 관리하면 AC를 받을 수 있다.
이상적인 도시 (Ideal City)
이 문제는 아주 핵심적인 아이디어 하나로 풀이가 사실상 종결된다. 문제에서 제시하는 이상적인 도시의 조건이 트리 구조를 말하고 있다는 점이다. 그러나 구멍만 없으면 여러 칸이 뭉쳐있을 수 있어 단순한 모델링으로는 사이클이 생긴다. 여기서 가로로 연속된 셀들을 묶는다면? 구멍이 없으므로 트리 구조가 될 것이고 이 트리 상의 거리는 정확히 두 셀 사이에서 세로로 이동해야하는 거리가 된다. 이 트리 상에서 모든 정점쌍 사이의 거리를 구하고 반대로 세로로 묶은 트리에서 거리를 구해 합치면 모든 셀 사이의 거리 합이 될 것이다. 트리에서 쌍 사이의 거리 합은 간선별로 이 간선을 지나는 쌍의 수를 생각하면 양쪽에 매달린 셀 수의 곱이 되므로 dfs 한번에 어렵지 않게 구할 수 있다.
timeismoney
이 문제는 그냥 풀기에는 곤란한 점이 너무 많다. 우선 두 종류의 값의 합의 곱이라는 목표는 그리디한 전략으로 고를 수 없기 때문이다. 만약 하나의 값만을 최소화하거나 둘의 합을 최소화한다면 그리디 전략이 통한다. 두 값의 가중치가 있어 '가중치가 곱해진 합' 정도만 되어도 문제를 풀 수 있다. 그럼 만약에 곱 조건을 합으로 바꿀 수 있다면 문제를 풀 수 있지 않을까? 문제의 t와 c값 상한이 255밖에 되지 않는다는 사실에 주목하며 문제를 변형해보도록 하자.
만약, 만들 수 있는 신장트리를 모두 구했고 각각에서 t값의 합=A, c값의 합=B를 구했다고 치자. 그리고 이 (A, B)들을 xy 평면에 플로팅한다면 어떻게 될까? 우리가 찾으려고 목표하는 점은 xy가 가장 작은 점이므로 답을 V라고 할 때 곡선 xy=V 보다 아래쪽 영역에는 점이 없을 것이다. 그리고 정확히 곡선 위에 AB=V인 (A, B)가 하나 이상 있을 것이다. 우리의 목표는 이 점을 찾아 내는 것이다. 여기서 한 가지 관찰할 수 있는 사실이 있다. xy=V는 볼록한 곡선이기 때문에 xy=V 아래에 점이 없다는 것은 이 곡선상의 (A, B)의 접선을 기준으로도 아래쪽에는 점이 없다는 사실이다. 이 사실이 의미하는 바는 어떤 (A, B)가 답의 후보이기 위해서는 적어도 xy=AB의 접선의 기울기에 대해 가장 아래쪽에 있어야 한다는 의미이다. 여기서 봐줘야 할 기울기의 후보 수를 생각해보면 수 범위를 X라고 할 때 (XN)^2 개라는 사실을 알 수 있다. 따라서 시간 복잡도는 O((XN)^2 * M lg M)이 된다. 하지만 아직도 TL 1초에는 어림도 없는 수준이다.
여기서 한 가지 사실을 더 관찰할 수 있다. 바로 후보가 되는 점들은 컨벡스 헐을 이룬다는 사실이다. 이 사실을 이용해서 분할 정복을 할 수 있다. 풀이를 하며 격자 위의 점들에 대해 이런 저런 관찰을 했지만 실제로 우리는 평면 위의 점들에 대해 어떤 정보도 알지 못하고, 단 한 가지의 연산만을 사용할 수 있다. 기울기 하나를 제시하고, 그 기울기의 직선에 대해 컨벡스 헐의 접점을 찾는 것이다. 우리는 우선 수직선과 수평선을 이용해 헐의 가장 왼쪽 점과 가장 아래쪽 점을 찾을 수 있다. 그리고 만약 연산으로 헐 위의 두 점을 잇는 기울기를 제시한다면 O(M lg M)에 헐 상에서 둘 사이에 있는 점을 임의로 하나 찾을 수 있다. 정리하자면, 왼쪽과 아래쪽, 즉 답이 있을 수 있는 영역의 앙 끝을 알고, 사이에서 임의의 점을 하나 찾을 수 있다. 사이의 한 점을 찾고, 그 점을 기준으로 두 구간을 나누는 작업을 반복해 분할 정복한다면? 헐 위의 모든 점을 찾을 수 있을 것이고 한 번의 연산으로 새로운 점을 하나 찾으므로 헐 위의 점만큼의 연산만을 사용할 것이다. 앞에서 관찰한 사실에 따라 이렇게 찾아진 점들 중 곱이 가장 큰 점을 찾으면 답이 된다.
시간 복잡도는 점이 존재할수 있는 좌표 영역이 XN*XN 그리드이므로 O(XN * M lg M)이 될 것이다. 그리고 XN항은 사실 컨벡스헐의 점 개수인데 그 상한이 (좌표범위)^(2/3) 이므로 실제로는 O((XN)^(2/3) * M lg M)이 되고, 어디까지나 상한이기 때문에 실제로는 더 작아 시간 안에 여유롭게 나온다.
Wild Boar
JOISC (JOI spring camp) 2018 day4
만약 뒤로 돌아갈 수 없다는 조건이 없다면, 문제는 각 점 쌍의 최단경로를 구하고 경로상에서 모두 더하는 식의 풀이가 될 것이다. 하지만 저 조건이 추가되면서 골칫거리가 생긴다. 지금 최단경로를 선택하면 다음에서 경로가 늘어나고, 반대의 경우도 가능한 상황처럼 말이다. 이 경우 여러가지 경우의 수가 생기는데, 이것이 첫번째 문제점이다.
하나씩 해결해보도록 하자. 우선 우리가 주목할 사실은 M<=2000으로 M도 작다는 사실이다. M이 작으면 단순한 정점 사이의 최단 경로가 아닌 양 끝 간선에 대한 정보를 담아 전처리해줄 수 있다는 점이 달라진다. 모든 정점을 각각의 차수만큼으로 쪼개 (a, u)의 페어로 만들 수 있다. 이는 현재 정점이 u는 u인데, 직전에 있던 점이 a라는 의미이다. 이러한 페어는 디그리 수의 합이므로 2M개가 나오게 될 것이다. 그리고 각 페어들을 새로운 정점으로 하여 모든 페어 사이의 최단거리도 O(M^2 lg M) 시간에 구할 수 있다. 이 전처리가 무슨 의미를 가지는지에 대해 생각해보면, L개의 정점을 순서대로 거칠 때 단순히 최단 경로를 붙이는 방법이 유효하지 않은 것은 해당 L개의 정점밖에 없기 때문에 유효하다는 사실을 알 수 있다. 무슨 의미냐 하면, 어떤 정점에서 다른 정점으로 움직일 때, 뒤의 경로와 충돌이 일어나는 상황은 양 끝밖에 없다는 의미이다. 따라서 a->b의 경로에서 우리는 a->u->...->v->b로 생각하고, u와 v만 결정해주면 ...에 해당하는 부분은 전처리한 (u, a)->(b, v)를 그대로 가져와도 된다.
전처리를 통해 문제가 단순해졌다. 이제는 s->t에서 내부의 경로를 고려할 필요가 없고, s->u->...->v->t의 u, v만 결정하면 된다. 하지만 u, v의 쌍이 많다는 것은 여전히 쿼리를 처리하기에는 무리이다. 따라서 u, v의 쌍을 줄일 필요가 있다. u와 v가 무엇에 영향을 받는지 관찰해보자. 만약 직전과 직후를 a, b로 둔다면 a->s->u->...->v->t->b의 경로가 될 것이다. 주어진 a, b에 대해 만족시켜야할 조건은 a!=u && b!=v 이기만 하면 된다. 따라서 우리는 a,b에 따른 최소 길이의 u,v를 찾으면 된다. 여기서 할 수 있는 발상은 대다수의 경우에서 s와 t를 잇는 최단 경로가 사용될 수 있고, a=u이거나 b=v일때만 사용하지 못한다는 점이다. 그럼 최단경로를 사용하지 못할 경우에 사용될 쌍을 second maximum과 같은 형태로 저장하면 되지 않을까?
위 발상을 통해 우리는 어떤 a, b에 대해서도 후보중에 최소가 있도록 u, v 쌍의 후보를 4개까지 줄일 수 있다. 우선 u1과 v1을 s와 t사이의 최단경로라고 두자. 그리고 u2!=u1 && v2!=v1 이면서 길이는 최소가 되도록 u2와 v2를 잡는다. 이렇게 하면 단 두 가지 경우를 빼고 어떤 a, b에 대해서도 최소를 가질 수 있다. 그 두 가지는 a=u1이고 b=v2일 때와 a=u2이고 b=v1일때이다. 이 경우 두 쌍 모두 사용할 수 없다. 따라서 저 경우를 커버할 수 있도록 두 조건을 뒤집어 u3!=u1 && v3!=v2, u4!=u2 && v4!=v1의 두 쌍을 후보에 넣는다. 이렇게 만들어진 4쌍은 어떤 a,b에 대해서도 최소를 반환할 수 있고 따라서 답이 되는 경로는 무조건 이 중에 있다. 후보의 조건을 생각하는 방법에 대해서는 표를 그리면 아주 쉽다. 임의의 행과 열을 하나씩 날릴 때 어떻게 날려도 남은 점 중 최소점이 찍혀있도록 점을 찍는다고 생각하면 된다.
마지막 남은 과제는 쿼리를 처리하는 방법이다. a->b->c가 있을 때, a->b의 경로 후보는 4개가 있을 것이고, b->c의 후보도 마찬가지로 4개가 있을 것이다. 그렇다면 둘의 경로를 조합하면 a->c의 경로 후보 16가지를 만들 수 있을 것이며, 여기서도 위와 같은 원리로 경로 후보 4개를 유지시키며 줄일 수 있다. 따라서 우리는 임의의 두 구간을 합칠 수 있다. 우리는 매 쿼리마다 하나의 구간을 바꾸고, 어떤 두 구간을 합칠때는 4^3의 상수 시간이면 충분하다. 따라서 세그먼트 트리로 경로들을 관리하면 쿼리 또한 O(Q lg L)의 빠른 시간에 처리할 수 있다. (큰 상수 4^3이 붙기는 한다.) 결론적으로 O(M^2 lg M + Q lg L) 시간에 문제를 풀 수 있다.