Petrozavodsk Summer 2019. Part 1

작년 가을에 버추얼 후기 느낌으로 적어놓고, 올리려고 하다가 여러 이유로 포스팅하지 않았던 글. 거의 1년동안 하드에서 잠자고 있던 텍스트다!

포스팅을 미룬 이유는 여러가지가 있다. 당연히 제일 큰 이유는 귀찮고 관심 없었기 때문이지만, 나름대로 통신교육 자료로 사용하려는 목적도 있었고, 업솔빙을 적당히 하고 보완해서 올리려는 목적도 있었다. 통신교육에는 이미 충분히 우려먹은 것 같아 별 상관이 없어 보이고, 업솔빙은 끝이 없을 것 같아서 그냥 올린다.

여담으로 여기 언급된 문제중 2019 가을 통신교육에 총 9문제가 사용되었다. 알아서 잘 찾아보자.

Day 5/6/8에 대해서는 Part 2에 적을 예정이다 (이건 적어 놓은 게 없다. 아주 먼 미래에 올라올 듯 :p) Day 3/4/7에 대해서는 딱히 코멘트 할 생각이 없다.

Day1 (Songyang Chen Contest 2)

6 / 848

• A (upsolved): 선형일때는 Segment Tree를 사용한 약간 복잡한 DP가 된다. 대충 손으로 해보고 (앞에서 한참 시간을 썼기 때문에 성급하게 결정을 내렸다) 트리에서도 똑같은 DP가 된다는 것을 깨달아서 포인터 segment tree를 구현하고 대회 시간을 넘겼다. 알고 보니 segment tree는 트리에서 확장하기가 쉽지 않으나, 사실 우리가 필요한 연산은 segment tree 없이 std::map 만을 사용해서 충분히 할 수 있는 연산이었다. 그렇게 선형일 때 이러한 유형의 DP를 꼭 세그트리를 쓸 필요가 없다는 사실을 깨닫고, map을 사용하여 그렇게 길지 않은 구현을 하고 맞았다. Max-flow로 모델링 한 후, min-cut을 그리디하게 푼다는 식의 접근법도 되는 것 같다.
• B (128+20): LIS 길이 기댓값은 $O(n^{0.5})$. 고로 서로 다른 답의 경우의 수도 저렇다. 분할 정복 하듯이 이진탐색을 batch로 하면 $O(n^{1.5}\log^2 n)$ 인데, 랜덤이라 그냥 적당히 잘 나왔다. 시간 제한 대비해 아주 빠른 접근은 아니다.
• C (-6, upsolved): Cographic matroid와 Choice matroid의 weighted maximum intersection이다. 이걸 짜고 열심히 TLE를 받았다. 상수 문제인지 구현 문제인지 도저히 모르겠고 아무리 코드를 봐도 어떤 부분을 고쳐야 하는 지 잘 모르겠어서 삽질 후 그냥 포기했다. 그리고 나중에 코드를 열어봤는데

snk가 변하지 않는다.

사람 맞냐... 아무튼 고친 후 AC. 이거 때문에 한 문제를 못 풀었을 뿐만 아니라 쉬운 문제가 무지막지하게 밀렸다.

• D (165): 모든 교집합이 존재하는 사각형 triple의 개수를 세는 문제인데, 개수 (즉 각 사각형마다 1) 을 세지 말고 영역의 합 (각 사각형마다 $nm$) 을 세라고 하면 문제를 2차원 부분합 배열에 간단한 수학 (double counting 느낌으로, 각 셀마다 그 셀을 포함하는 삼각형 쌍을 셈) 으로 해결할 수 있다. $nm$ 을 세는 것과 비슷한 방식으로, $(n-1)m, n(m-1), (n-1)(m-1)$ 도 셀 수 있다. 가로/세로 길이를 각각 하나씩 줄이면 되기 때문이다. 어? $nm - (n-1)m - n(m-1) + (n-1)(m-1) = 1$. 진짜 신기한 문제였다.
• E (15): KOI 2014 금광
• F (51): 좌표 압축 후 잘. 제한이 작아서 정수론은 필요없음
• G (upsolve): APIO 2018 Circle selection과 비슷한 트릭이다 기본적으로는. 이건 너무 길어서 아래에 따로 글로 작성한다.
• H (146+20): 적당히 $k \oplus n$ 이 작다고 guess한 후, $k \oplus n$ 을 작은 값부터 fix해서 시간 제한동안 brute-force하면 풀리는 전형적인 ㅈ수론 문제
• I (upsolve): 가중치가 없으면 Robinson-Schensted Correspondence. 신기한 이론인데 공부해 보면 좋을 것 같다. 가중치가 있으면 이런 저런 알고리즘 퍼즐이 붙는다. 문제와 상관 없이, 독립적인 퍼즐로 소개할 만한 것은 이것인 것 같다. Weighted LIS를 세그먼트 트리 없이 구하려면 어떻게 해야 할까? 가중치가 양의 정수라면 해당 가중치 갯수만큼 숫자를 복사해서 길이가 $\sum_{i = 1}^{N} W_i$ 인 수열을 만들자. 여기서 단순히 이분 탐색을 사용해서 LIS를 구하면 느리지만 올바른 풀이를 얻을 수 있다. 이 때 해당 컨테이너를, 같은 수 여러개를 (숫자, 개수) pair로 관리하는 식으로 효율화시키면, amortized $O(n \log n)$ 에 Weighted LIS를 세그트리 없이 구할 수 있다. 물론 이걸로 Weighted LIS를 구하는 건 쓸데없다. 하지만 이 상황에서는 Robinson-Schensted Correspondence에서 관리하는 Young tableux가 정확히 저 RLE 컨테이너가 되기 때문에, 저런 식으로 컨테이너를 관리하면 일반화가 가능해진다.
• K (203+100): 옛날에 CERC에 나왔던 문제 (다를수도 있으나 하튼 그 때 생각하면서 풀었다) 를 귀찮게 변형한 버전이다. 업솔빙 당시에는 CERC 문제의 정해인, 복잡한 small-to-large 그리디 외에는 풀이를 몰랐다. 그리고 WA를 참 많이 받았다. 주말교육에서 tlwpdus에게 간단한 풀이를 들었는데, 아주 아름답고 간단하게 설명 가능한 풀이가 있고, 이 문제 외에도 여러 문제에 적용할 수 있는 테크닉에 관한 풀이라서, 매우 재밌게 들었던 것 같다. 하여튼 이런 저런 교육을 거치면서 요즘은 나름대로 파훼법이 알려진 웰노운 문제가 된듯. https://github.com/justiceHui/Unknown-To-Wellknown/blob/master/README.md 의 Monster Hunter / Escape 유형 참고.

Day2 (GP of Kazan)

• A: Should upsolve.
• C: Cactus DP without cactus
• D: 재밌는 문제. 트리나 선인장에서 행렬식을 구하는 것은 simple DP로 된다. 이 경우에는 각 BCC의 크기가 작은데, 위 DP를 합쳐주는 방법을 그냥 gaussian elimination으로 하면 된다.
• E: Linear matroid라서 최대 독립 집합을 $O(QN^3/64)$에 찾을 수 있다. 이건 느린데, 빼야할 것이 무엇인지는 해당 숫자를 넣었을 때 생기는 unique한 circuit을 찾아주면 최솟값을 찾아서 지워주는 식으로 알 수 있다. 저 circuit을 $N^2/64$ 에 찾으면 된다.
• F: 저 때는 몰랐는데 비슷한 문제가 이미 백준에 있었다. 이름하여 머그컵의 놀이기구2...
• H: 꼭 풀어보자.
• I: Edge centroid decomposition. 이걸 사용하면 general하게 HLD나 centroid decomposition을 $O(\log N)$ 에 할 수 있다고 하는데 잘 모른다.
• J: Augmenting Path를 Tree DP로 구하면 $O(N^2)$ 이다. 이제 이걸 HLD로 줄이면 $O(N\log^2 N)$ 에 풀 수 있다. 화이팅!

Day9 (MSU AESC Contest)

• 5 / 391
• I (20min): BFS 트리에서 깊이 차가 1 초과인 정점을 잇는 간선은 없음. 그래서 mod 3만 줘도 BFS 트리에서 어떤 역할을 하는 지 알 수 있다. outdegree가 없는 정점 하나를 찍으면 된다 (답은 유일). 이 문제를 베껴서 카이스트 대회에 출제한 문제가 이것. 이렇게까지 대놓고 베끼고 싶지는 않았지만, 쉬운 문제가 급했다..
• F (55min): 적당히 역순으로 만들어나가면 됨. $n$ 을 만들려면 루트 정도 크기의 정수 2개가 있으면 됨. $2^{\log \log n}$ 정도 의 스텝이 필요하니 $O(\log n)$ 정도면 풀 수 있음. 제대로 된 증명은 잘 모르겠고 그냥 짜증나는 문제
• H (77min): I번과는 반대로, 이 문제는 아마 카이스트 대회에서 베껴서 출제한 것 같다 (...) 답에 대해 이분 탐색 후 Dev, Please Add This 와 동일한 아이디어로 2-SAT을 구성하면 된다. 난 $2n$ 개의 변수를 사용한 2-SAT을 생각했는데 이렇게 하면 상수가 엄청 커져서 $n$ 개로 줄이는 아이디어를 생각해 낸 후 맞았다 ㅠㅠ
• E (88min): $S_i = {v | x_v \le i}$ 인 집합이라고 하면, 결국 $S_{i+1} \subseteq S_i$, $|S_i| \le s$ 라는 제약 조건 하에 $\sum_{i} |E[S_i]|$ 를 최대화하는 것과 동일한 문제이다. $E[X]$ 는 $X$ 에 양 끝점이 모두 들어간 간선의 집합을 뜻한다. 사실 포함 제약 조건이 없으면 그냥 $|S_i|$의 합을 최소화 하면서 $|E[S_i]|$ 의 합을 최대화하는 것이기 때문에, 고정된 정점 부분 집합의 크기에 대해서 $|E[X]|$ 의 최댓값을 계산하고 냅색을 하면 된다. 포함 조건이 있어서 그런데, $|E[X]|$ 는 cut function이라 submodular function이다. 고로 그냥 하면 된다 (...) 정해는 이 관찰이 없어서, 포함 제약 조건을 인지하고 그냥 냅색을 한다.
• C (151min): Centroid의 위치를 알면, centroid decomposition을 통해 $O(q\log n)$ 에 답을 구할 수 있다. Centroid만 알면 된다. 주어진 정점을 dfs order로 정렬한 후 중간값이 되는 정점을 고르면, Centroid는 그 정점과 루트 간의 경로 상에 존재한다. 중간값은 잘 알려진 Running median 문제이고 (Fenwick tree가 가장 간단하다) 이후 Centroid를 찾는 건 sparse table에서 이분탐색하면 된다.
• G (upsolved): 뭔가 어려운 DP였다.
• D: 는 업솔브 해야 함. 그나저나 최근에 300iq가 이런 걸 만들었다 (...)

Detailed solution to Day1G

풀이를 설명하기 전에 다음과 같은 단순화를 하겠습니다.

• $1 \ldots k$ 번째 거리를 전부 구하는 것이 아니라 $k$ 번째 거리만을 구함

• 모든 구의 반지름이 동일함

답에 대한 이진 탐색을 통해서 문제를 해결합시다. 두 구 간의 거리가 $X$ 이하인 쌍의 개수를 세는 알고리즘은, 각 구의 반지름을 $X/2$ 로 늘린 후, 서로 닿는 두 구의 쌍의 개수를 세는 알고리즘과 동일합니다. 고로, 각 구의 반지름을 $X/2$ 만큼 늘리고 시작합시다. 이 경우에도 모든 구의 반지름이 동일하다는 사실은 변하지 않습니다.

모든 구의 반지름을 $R$ 이라고 하였을 때, 단순한 알고리즘은 모든 서로 다른 구 쌍을 열거한 후 두 중심의 거리가 $2R$ 이하인지 확인할 것입니다. 이를 최적화합시다. 각각의 구를 $2R \times 2R \times 2R$ 크기의 정육면체 버킷 으로 나눌 수 있습니다. 즉, $(x, y, z)$ 를 중심으로 하는 구는 $(\lfloor \frac{x}{2R} \rfloor,\lfloor \frac{y}{2R} \rfloor,\lfloor \frac{z}{2R} \rfloor)$ 위치에 있는 버킷에 속합니다. 이렇게 버킷으로 구를 나누면, 중심의 거리가 $2R$ 이하인 구 쌍은 버킷의 $x, y, z$ 좌표 차이가 많아야 1밖에 나지 않습니다. 고로, 어떠한 점에 대해서 답을 찾고자 할 때, 이 점 근처에 있는 27개의 버킷에서만 완전 탐색을 돌리는 커팅을 생각해 줄 수 있습니다. 이러한 완전 탐색은 Hash map을 사용하여 구현할 수 있습니다.

이 커팅은 효율적이지 않아 보이지만, $k$ 가 작다는 사실을 생각해 봅시다. $k$ 가 작기 때문에 이미 $k$ 개의 교차를 확인했으면 단순히 쌍의 개수가 $k$ 개 이상이다 라고 한 후 프로그램을 종료해 줄 수 있습니다. 이 사실과 종합하였을 때 다음과 같은 Lemma를 유도할 수 있습니다:

• Lemma. 하나의 $2R \times 2R \times 2R$ 큐브에 $k$ 개 미만의 교차를 갖게 하면서 최대한 많이 점을 넣으려고 한다면, 최대 $O(\sqrt k)$ 개의 점만을 넣을 수 있다.
• Proof. 버킷을 8등분하였을 때 각 8등분된 정육면체 안에 많아야 $2\sqrt k$ 개의 점이 들어갈 수 있기 때문입니다.

고로, 특정 버킷에서 $O(\sqrt k)$ 개 이상의 원소를 탐색했다면 프로그램은 자연스럽게 종료하게 되어 있습니다. 각 버킷에서 다른 버킷을 탐색하는 횟수는 많아야 $O(\sqrt k)$ 개이니, 다른 버킷의 기준에서 자신의 버킷을 탐색하는 횟수 역시 $27 \times O(\sqrt k) = O(\sqrt k)$ 가 됩니다. 고로 총 시간 복잡도 $O(n\sqrt k)$ 에 이분 탐색의 정답을 판별할 수 있습니다. (숨겨진 상수가 매우 크다고 생각할 수 있으나 최악의 경우가 나오는 것이 매우 힘들어서 오히려 작은 편입니다.)

이제 위에서 한 단순화를 단계적으로 없애 봅시다. 첫 번째로 모든 구의 반지름이 동일하지 않다고 합시다. 모든 점을 거리 감소순으로 정렬한 후, 반지름이 큰 구 쪽에서 작은 구 쪽으로 루프를 돌린다고 합시다. (즉, 어떠한 구에 대해 답을 계산할 때 자신보다 반지름이 큰 구는 무시합니다.) 위 알고리즘에서 $R = max(r_i)$ 라고 두고 똑같은 과정을 반복하면, 정확한 알고리즘은 찾을 수 있으나 Lemma가 깨지게 되어 시간 복잡도가 틀리게 됩니다.

하지만, 교차의 기준을 “거리가 $2R$ 이하” 가 아니라 “거리가 $R/2$ 이하” 라고 바꾼다고 하더라도 위 Lemma는 여전히 옳습니다 (똑같은 방법으로 증명하시면 됩니다). 교차의 기준이 $R/2$ 이하라면, 만약 탐색하는 쪽의 구의 반지름이 $[maxr / 2, maxr]$ 안에 있다면, 실제 교차 기준을 만족하면 무조건 거리가 $R/2$ 이하가 됩니다. 고로 해당 범위의 구에 대해서는 여전히 같은 시간 복잡도를 보장합니다. 이제 탐색하다가 위 구간을 벗어나게 되는 것이 문제인데, 지금 현재 탐색 순서는 반지름이 큰 구에서 작은 구 쪽으로 설계되어 있습니다. 고로 구간을 벗어난 첫 구에 대해서, 해당 구보다 반지름이 큰 구들을 전부 무시해 주면 되니, 그냥 똑같은 것을 계속 반복하면 됩니다. 시간 복잡도에 추가 $\log r$ 이 붙어 $O(n \sqrt k \log r)$시간에 문제를 해결할 수 있습니다.

두 번째로, $1 \ldots k$ 번째 거리를 전부 구해봅시다. 위 알고리즘은 특정 거리에 대해서 $k$ 개의 쌍을 찾지 못했다면, 해당 거리 이하의 가까움을 가진 모든 쌍을 열거하게 됩니다. 고로, $k$ 번째 거리를 $X$ 라고 하면, $X-1$ 에 대해서 위 알고리즘을 실행합니다. 위 알고리즘은 실패하는 대신 거리가 $X-1$ 이하인 모든 쌍을 열거하니, 이 정렬된 리스트의 길이가 $m$ 이라면, $k-m$ 개의 $X$ 를 뒤에 붙인 후 출력하시면 됩니다.