2022 ICPC Seoul Regional

티스토리 뷰

공부/Problem solving

2022 ICPC Seoul Regional

구사과 2022. 11. 23. 00:56

이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 별 일 없다면 상위 3팀이 진출할 것이다.

서울대학교: C14H9Cl5
KAIST: BabyPenguin (World Finals 진출 확정)
숭실대학교: NLP (World Finals 진출 매우 유력)
POSTECH: 000102 (World Finals 진출 가능성 약간 존재)
고려대학교: I hate PS

코로나19로 인해 2020 World Finals가 1년 반 정도 연기된 관계로, 2022 및 2023 World Finals는 이집트에서 한번에 진행한다. 서울대학교 1등 팀인 C14H9Cl5는 FSM과 동일한 멤버로 구성된 팀으로, 이번 대회를 통해 2022, 2023 World Finals의 진출 자격을 모두 얻었다.

World Finals의 정책 상, FSM/C14H9Cl5는 2022/2023 대회 중 하나의 대회만을 참가할 수 있고, 고로 남은 한 대회에는 서울대학교의 다른 한 팀이 참가할 수 있다. 이 다른 팀이 어떠한 팀인지는 결정된 것이 없고, 2021 서울대 2등 팀인 The Elders, 혹은 2022 서울대 2등 팀인 HappyLastDance 중 한 팀이 참가할 것으로 전망된다.

Mirror postmortem

나는 jwvg0425, rkm0959 와 함께 미러 대회에 참가했다. 대충 타임라인은 이랬던 것 같다.

90분까지는 그냥 ADEFIJK를 각자 열심히 밀었다. E 디그리 조건 없는 줄 모르고 한 30분쯤 코딩했다. $n, m$ 바꾼거 때문에 디버깅한 시간도 포함
이후 jwvg님은 L을 풀고, 나는 C를 풀고, rkm이 B/H를 봤다.
jwvg님이 L 풀이를 거의 찾았는데 모든 사이클 길이가 다를 때가 살짝 애매했다. 내가 해당 케이스에 대해 틀린 풀이를 내고 "나를 믿으라" 고 했다. jwvg님이 이걸 구현한 후 WA를 받았고, 반례까지 찾아줬다 (...). 그래서 대충 수정하는 방법을 고안하고, 증명 또 안 하고 "나를 믿으라" 를 한번 더 시전했다 (......). 다행이도 그건 맞았고, 실제로도 반례 없는 풀이었다.
C를 코딩하는데 별로 안 걸렸는데 예제가 안 나왔다. 예제가 디버깅하기 좀 큰 사이즈고, 나이브라고 짤 만한게 애매하고, 풀이를 아무리 고민해봐도 틀린 부분이 없고, 코드도 짧아서 한 1시간쯤 보다가 결국 풀 수 없음을 선언하고(!) rkm에게 맡겼다. rkm이 반례를 찾아줬는데 내가 예상하지 못한 방향에서 알고리즘이 틀렸었다. 어떻게 허겁지겁 고쳐서 맞았다. 이 문제만 2시간 걸렸다. 2시간!
남은 시간 jwvg님과 같이 B를 풀었고 아마 정해같은 풀이가 나왔던 거 같은데 WA가 떴다. 이건 이 글 쓰기 직전에 고쳤는데, 글에도 쓴 $t = 2$ corner case를 예외처리하지 못한 것이 화근이었다.
rkm은 H 풀이가 나왔고 코딩도 꽤 했는데, 증명 안 한 부분에서 TLE가 날 거 같다고 중간에 포기했다. 근데 사실 그 부분은 내가 TLE 안 날 거 같다고 "나를 믿으라" 라고 했던 부분이었는데, 아마 내가 앞에서 하도 헛다리를 짚어대니 신앙심이 떨어진 것 같다. 아쉽게도 이번에는 내가 진짜 맞았고, 대회 후 그 부분을 내 말대로 나이브하게 구현하니 (그리고 버그를 좀 고치니) AC가 나왔다.

돌아보니까 너무 못 해서 할 말이 없다. 사실 이날 미러 치려고 대전에서 평소보다 서너시간 일찍 기상해서 서울에 올라왔는데, 약간 컨디션 탓을 하고 싶기는 하다. 이 정도로 못했는데 B, H를 거의 풀 뻔했을 정도로 팀운이 좋아서 아쉬움이 더 많이 남는 것 같다. 하튼 그래도 결과적으로 보면 쟁쟁한 팀들 상대로 나름 경쟁력 있게 잘 했다고 생각한다.

Problem analysis

올해 문제의 난이도는 작년과 유사한 수준으로 꽤 어려운 편에 속한다. 체감상은 작년보다도 약간 더 어려운 느낌인데, 스코어보드로는 그렇게 보이지 않는다는 점에서 참가 팀의 수준이 높아졌다고 느꼈다.

일부 문제들은 구현했으며, Github 에 icpc22_ 로 시작하는 이름으로 AC 코드를 업로드하였다.

A. Card Game

두 가지 단순화를 적용하여 전형적인 게임 문제로 변형할 수 있다.

첫 번째 단순화는 대각선 조건을 지운다. 카드를 제거하는 규칙이 "격자의 대각선" 이면 모델링하기 복잡하다. 일반적으로 대각선을 사용하는 문제들은 격자를 45도 돌려서 수평선/수직선으로 변환할 수 있다. 이 문제의 경우도 그러한 테크닉을 사용할 수 있다. 입력 격자를 45도 돌리면, 다음과 같이 규칙이 바뀐다:

격자를 체스판처럼 흑/백으로 칠할 경우, 흑색 칸에 있는 카드와 백색 칸에 있는 그리드는 독립이다.
빨간 카드는 수평선 상의 연결된 카드들을 제거한다. (수평/수직은 돌리는 방법 따라 다를 수 있다.)
파란 카드는 수직선 상의 연결된 카드들을 제거한다.
초록 카드는 수평선 및 수직선 상의 연결된 카드들을 제거한다.

두 번째 단순화는 "연결된 카드" 조건을 지운다. 격자를 45도 돌리긴 했지만, 여전히 한 수평선과 수직선에 있는 카드들은 연속한 그룹을 이룬다. 고로 어떠한 선 상에 있는 연결된 카드를 지운다는 것을, 그냥 해당 수직선을 전부 비우고 수직선 양 옆에 대해서 독립적으로 문제를 분할한다고 생각해도 무방하다.

이러한 두 가지 단순화를 거쳤고, 또한 그런디 수 (Grundy number) 에 대한 지식이 있다면, DP를 사용하여 문제를 해결할 수 있다. 위에 있는 모든 연산들은 직사각형 영역에 있는 카드 그룹을 더 작은 직사각형 영역으로 나눈다. $DP[sx][ex][sy][ey]$ 를, $[sx, ex] \times [sy, ey]$ 직사각형 에서 게임을 했을 때의 Grundy number 반환값이라고 하자. 각 위치에 있는 카드들을 하나씩 제거해보고, 이에 따른 독립적인 상태들을 XOR로 합쳐준 후, 이 결과들의 MEX를 반환하면 된다. 이 DP의 시간 복잡도는 $O((NM)^3)$ 이다.

여담으로 BOJ 16883. 대각 게임 문제와 거의 동일하다.

B. Castle Design

문제에서 정의한 turn sequence를 보면서 몇 가지를 관찰해야 한다. 첫 번째로 관찰할 수 있는 것은, L의 개수가 R의 개수보다 항상 정확히 4개 많아야 한다는 점이다. 두 번째로는, $t = 2$ 인 경우에는, turn sequence에 "RR"이 등장해서는 안 된다. 대신 "LL" 이 정확히 4번 등장하고, 그 사이는 LRLR... 의 꼴이 반복되어야 한다. 이때 "LL" 은 해당 도형의 동서남북 방향 끝점을 상징함을 볼 수 있다.

이 관찰을 통해서 $t = 2$ 인 경우에 대한 직관을 어느 정도 얻을 수 있는데, 대략 그 모양이 마름모와 같이 되어 있어서 LRLRLR... 형태의 대각선 체인이 변을 나타내고, LL 인 지점이 모서리를 나타냄을 알 수 있다. LL인 지점을 기준으로 turn sequence를 쪼개면, 각 마름모 변의 길이 를 알 수 있다. 그렇다고 각 변에 정확히 1의 길이를 부여할 경우 변들이 맞지 않을 수 있으니, 특정 변의 길이를 적당히 늘려서 길이를 맞춰야 할 것이다.

이 부분은 가로 축과 세로 축을 쪼개서 생각하면 깔끔하다: 마름모를 위쪽 / 아래쪽 반으로 쪼갤 경우 마름모가 가져야 하는 최소 가로 길이를 계산할 수 있고, 왼쪽 / 오른쪽 반으로 쪼갤 때도 최소 세로 길이를 계산할 수 있다. 이 최소 길이를 만족하게, 다른 변들을 적당히 늘려주면 그것이 최적의 구성임을 알 수 있다. 고로, $t = 2$ 인 경우 $O(n)$ 시간에 각 변의 길이 를 계산한 후 이를 토대로 최소 가로/세로 길이를 계산하고, 둘의 합의 2배를 출력하면 된다. 다만 마름모 변의 길이가 너무 잘 맞는 경우에는 변이 서로 맞물려서 simple polygon이 안 나오는 Corner case가 있음에 유의하라. 예를 들어 LLLRLLLR 과 같은 입력이 있다.

$t = 1$ 일 때는 주어지는 turn sequence가 한쪽 축에만 단조적이다. 첫 번째 단계는 이 단조적인 축을 기준으로 turn sequence를 위/아래로 쪼개는 것인데, $t = 2$ 인 케이스와 다르게 이 부분이 항상 LL 과 같이 깔끔하게 나오지는 않는다. 고로 이 부분을 먼저 찾아야 한다.

turn sequence를 기준으로 다각형을 한 바퀴 돌면, L - L 사이를 지날 때의 방향을 모두 계산할 수 있다. 다각형이 $x$ 축에 단조적이라면, $x$ 축에 수직인 방향으로 (즉, 위 아래 방향으로) L - L 사이를 움직이는 일이 정확히 두 번만 일어나고, 단조적이지 않다면 그렇지 않다. 고로, 모든 L - L 에 대해서 그 사이를 지나는 방향이 평행한 축을 메모해 두고, 해당 메모에서 정확히 두 번 등장한 축을 지나는 LL 을 기준으로 turn sequence를 위와 아래로 분할할 수 있다. 이렇게 turn sequence를 파싱했으니, 이제 이 정보를 토대로 문제를 해결하면 된다.

일반성을 잃지 않고, 다각형의 위쪽 영역의 길이가 아래쪽 영역의 길이보다 크거나 같다고 하자. 몇 가지 시도를 해 보면, 최적해에 다음과 같은 성질이 있음을 알 수 있다:

가장 왼쪽/오른쪽에 있는 세로 선분을 제외한 모든 세로 선분의 길이는 1이다.
- 만약에 세로 선분의 길이가 2 이상이면, 한 쪽을 높여주고 이 길이를 가장 왼쪽/오른쪽으로 넘겨주면, 위쪽 껍질과 아래쪽 껍질간의 거리를 늘리면서 둘레 길이를 유지할 수 있다.
위쪽 영역의 가로 선분의 길이는 모두 1이다.
- 이건 엄밀하게 증명하지는 않았다 (정말 하기 싫을 거 같다). 다만 직관적으로는 꽤 그럴듯하다고 생각한다. 가로 선분이 2 이상인 건 두 껍질이 만나기 때문에 공간을 띄워줘야 해서일 것인데, 두 껍질이 만날 때 가로로 공간을 띄우는 것보다는 세로로 공간을 띄우는 게 더 유리하다: 두 껍질이 길이 1 선분 하나를 두고 딱 붙어있다면, 가로로 공간을 띄우려면 두 칸을 띄워야 하는데 세로로 띄우려면 한 칸만 띄우면 된다. 한쪽 껍질에서 툭 튀어나와서 가로로 띄워야만 하는 경우는, 세로 선분의 길이가 모두 1이기 때문에 있을 수 없다.

이 가정을 토대로 $O(N^2)$ DP 식을 세울 수 있다. 일단 세로 선분의 길이가 모두 1이니, turn sequence를 각 가로 선분의 높이를 저장하는 정수열로 변환해 주자. $DP[i][j]$ 를, 현재 단조 다각형의 가로 $i$ 개 영역을 처리했고 (고로 위쪽 영역이 $i$ 번 가로 선분으로 끝나고), 아래쪽 영역이 $j$번 가로 선분으로 끝날 때, 왼쪽 세로 선분이 늘려져야 하는 최소 길이라고 하자. 위쪽의 가로 $i$ 번 선분과 세로 $j$ 번이 만날 때 필요한 최소 여백 길이를 $cost(i, j)$ 라고 하면, $DP[i][j] = max(min(DP[i - 1][j], DP[i - 1][j - 1]), cost(i, j))$ 와 같은 점화식이 나온다. 이는 쉽게 계산할 수 있다. 왼쪽 세로 선분이 늘려져야 하는 길이를 알면, 오른쪽 세로 선분의 길이 역시 역산할 수 있고, 가로 길이는 결국 위쪽 껍질의 길이와 동일하니, 모든 정보를 계산할 수 있다.

여담으로 논문 이 있는 문제고, kdh9949 블로그에 의하면 2016년 IOI 선발고사 문제였던 것 같다. 내가 웬만한 문제, 특히 선발고사는 다 기억하는데 이게 내가 친 선발고사에 있는 줄은 몰랐다. 나중에 찾아보니 당시 1차 선발고사때 딱 3문제 풀어서 400점 만점에 300점 받았는데, 0점 받은게 이거였다. LRLR 주는 문제 너무 많아서 그만 기억하고 싶었을 수도 있다.

C. Empty Quadrilaterals

빈 사각형을 세는 건 어려울 수 있으나, 빈 삼각형을 세는 것은 어렵지 않다. 시작에 앞서서 빈 삼각형의 개수를 세는 방법을 잠시 짚고 넘어가자. 여담으로 이 부분은 USACO 삼각형 영역 문제의 풀이와 상당히 겹치니 해당 문제를 참고해도 된다.

삼각형의 한 변 $i, j$ 를 고정시키고, 일반성을 잃지 않고 $ccw(a[i], a[j], a[k]) > 0$ 인 점 $k$만을 고려하자. 각 점 $k$ 에 대해서, $(i, j, k)$ 삼각형 안에 점 $l$이 있다는 것을 다음과 같이 표현할 수 있다:

$ccw(a[i], a[l], a[k]) < 0$
$ccw(a[j], a[l], a[k]) > 0$

모든 해당되는 $k$ 에 대해서, $ccw(a[i], a[x], a[y]) > 0$ 인 순서로 정렬한 후, 정렬된 배열에서 $k$ 의 인덱스를 $x(k)$ 라고 하자. 비슷한 방식으로, $ccw(a[j], a[x], a[y]) < 0$ 인 순서로 정렬한 후, 정렬된 배열에서 $k$ 의 인덱스를 $y(k)$ 라고 하자. 그렇다면 $(i, j, k)$ 삼각형 안에 점 $l$이 있다는 조건을 다음과 같이 다시 쓸 수 있다:

$x(l) < x(k), y(l) < y(k)$

이 값은 $x$ 에 대해 스위핑한 후 펜윅 트리로 셀 수 있다. 고로 모든 삼각형에 대해 그 안에 들어가는 점의 개수를 알 수 있고 이에 따라 빈 삼각형의 개수 역시 알 수 있다. 총 시간 복잡도는 $O(n^3 \log n)$ 이다.

볼록 사각형의 경우 두 개의 대각선이 있고, 오목 사각형의 경우 한 개의 대각선이 있으며, 두 경우 모두 대각선 양 옆에 빈 삼각형을 붙이는 식으로 조합된다. 즉, 모든 대각선 후보에 대해서, 이 대각선의 왼쪽 / 오른쪽에 붙을 수 있는 삼각형의 경우를 세면, (볼록 사각형) * 2 + (오목 사각형) 의 개수를 셀 수 있다. 대각선 하나에 대해서 양 옆에 붙일 수 있는 빈 삼각형의 개수는 위와 정확히 같은 방법으로 각 선마다 $O(n \log n)$ 에 셀 수 있고, 고로 (볼록 사각형) * 2 + (오목 사각형) 라는 값을 $O(n^3 \log n)$ 시간에 계산할 수 있다.

하지만 우리가 원하는 답은 (볼록 사각형) + (오목 사각형) 이기 때문에 이것으로는 아직 부족하다. 조금 더 생각해보면, 빈 오목 사각형의 개수 역시 셀 수 있음을 알 수 있다. 어떠한 대각선 $i, j$ 에 대해서 두 점 $k, l$ 이 이루는 오목 사각형이 비어있다는 것은, $(i, j, l)$ 안에 있는 점의 개수가 $(i, j, k)$ 안에 있는 점의 개수보다 정확히 하나 작으며, 그 점이 $l$ 이라는 것을 뜻한다. $count(k)$ 를 $(i, j, k)$ 안에 있는 점의 개수라고 하면, 이는

$x(l) < x(k), y(l) < y(k)$
$count(l) = count(k) - 1$

이 된다. 여기서 관찰해야 할 것은, $count(l)$ 이 같은 점들은 $x(i)$ 가 증가하면 $y(i)$ 가 감소하는 경향성을 띈다는 것이다. 고로 $count(l)$ 이 같은 점들을 $x(i)$ 가 증가하는 순으로 나열하면, $x(l) < x(k), y(l) < y(k)$ 를 만족하는 점은 연속된 구간을 이루며, 이 구간은 이분 탐색을 통해서 찾을 수 있다. 고로 오목 사각형의 개수 역시 셀 수 있으며, 이렇게 구한 두 값을 합한 후 그 절반을 계산하면 된다.

사실 여기까지 구현하고 난 시간 초과를 받았는데, 이는 각도 정렬이 꽤 느려서 그렇다. 모든 $i, j$ 에 대해서 $ccw(a[i], a[j], a[k]) > 0$ 인 $k$ 를 따로 구해서 정렬하지 말고, 각 $i$ 에 대해서 모든 점을 360도 각도 정렬한 후 이 결과를 사용해서 $x(k), y(k)$ 를 $O(n)$ 에 구해주면, 각도 정렬을 $O(n)$ 번만 해도 되어서 더 효율적이다. 이를 더 최적화하면 $O(n^3)$ 에도 해결할 수 있으나, 이 정도의 최적화는 필요하지 않다.

D. Folding Stick

$O(n^2)$ 동적 계획법을 고안한 후 자료 구조로 최적화하는 꽤 전형적인 형태의 문제이다. $dp[i]$ 를, 막대의 맨 앞 $i$ 개 조각을 최적으로 접었을 때, 마지막 조각의 길이로 가능한 최소라고 정의하자. $a_i$ 를 맨 앞 $i$ 개 조각의 길이 합 이라고 할 때 (부분합 배열이다), 다음과 같은 점화식을 얻을 수 있다:

$dp_i = min_{j < i, dp_j \le a_i - a_j} (a_i - a_j)$

이 점화식을 계산한 후 답이 $dp_n$ 이 되지는 않는다. 마지막 조각은 그 전 조각보다 길이가 길 필요가 없기 때문이다. 마지막 조각의 시작점을 $i$로 두고 전부 순회하면, 문제의 정답은 $min_{0 \le i \le n} max(dp_i, a_n - a_i)$ 가 된다. 고로 문제는 $dp_i$ 를 빠르게 계산만 하면 해결할 수 있다.

$dp_i$ 항 하나를 계산할 때, 우리는 $dp_j + a_j \le a_i$ 를 만족하는 모든 $j$ 중 $j$ 를 최대화하는 것이 무엇인지를 알고 싶다. $a_i$ 가 증가하기 때문에, 한번 어떠한 $j$ 가 답의 후보가 될 경우 이 $j$ 는 계속 답의 후보가 된다. 고로 $dp_j$ 가 계산은 되었지만 아직 답의 후보가 되기에는 이른 것들을 적당한 자료구조에 넣은 후, $dp_j + a_j$ 가 작은 순서대로 자료구조에서 뽑아가며 답의 후보를 늘려주면 된다.

이 역할에 가장 적합한 자료구조는 Heap (Priority Queue) 이다. $dp_i$ 를 계산한 이후, $(dp_i + a_i, i)$ pair를 min-heap에 넣는다. 매번 $dp_i$ 를 계산할 때, pair의 첫 번째 값이 $a_i$ 보다 작은 것들을 모두 뽑으면서, 가능한 $j$ 중 최대 인덱스를 관리한다. 이후 이 인덱스에서 상태 전이를 해 주면 된다. 이렇게 하면 시간 복잡도는 Heap 자료구조에 의해 결정되니 $O(n \log n)$에 문제를 해결할 수 있다.

E. Forbidden Turns

간선과 간선 간의 이동에 대한 제약조건이 붙어있다는 점에 착안해서, 간선을 정점으로 한 그래프를 생각할 수 있다. 입력으로 주어진 그래프가 정점 집합 $V$, 간선 집합 $E$ 를 가진다면, 다음과 같은 방법으로 새로운 그래프를 만든다:

각 간선 $(u, v) \in E$ 를 새 그래프의 정점으로 한다.
만약 $(u, v, w)$ 가 forbidden turn 으로 주어지지 않는다면, $(u, v) \rightarrow (v, w)$ 를 새 그래프의 간선으로 둔다. (이 조건은 std::set 등으로 판별하면 된다.)

이 경우 새 그래프의 정점은 $m$ 개이고, 간선은 각 정점의 indegree * outdegree 합만큼 생긴다. 잘 읽어보면 각 정점의 outdegree가 최대 10이라서, 새 그래프의 간선은 $10m$ 개 정도임을 알 수 있다. 이제 이 그래프에서, 시작점이 $s$ 인 모든 간선들을 source로 하는 Dijkstra's algorithm을 사용하면, 도착점이 $t$ 인 모든 간선들까지 도달하는 데 걸리는 최단 시간을 알 수 있고, 이를 토대로 답을 계산하면 된다. $s = t$ 인 예외 케이스에 유의해야 한다.

여담으로 $n, m$ 이 아니라 $m, n$ 순서로 주어져서 아주 고생했다. 그리고 간선의 outdegree가 최대 10이라는 내용을 거의 숨겨놓고 지문을 작성해서, 나는 해당 조건이 빠진 채로 문제를 해결했다. 해당 조건이 없는 버전은 자료구조를 열심히 쓰면 풀 수 있는데 짧게 설명하기 어려워서 생략한다. 대충 이런 방법과 유사하다.

F. Frog Jump

매 쿼리마다 개구리가 해야 하는 이동의 총 길이는, 현재 위치와 도착 위치 사이에서 구간으로 덮이지 않은 수직선의 길이이다. 현재 위치와 도착 위치는 대응되는 구간의 아무 위치 (예를 들어 시작점) 으로 간주해도 무방하니, 결국 문제는

덮이지 않은 수직선 구간들을 모으고
두 점이 주어질 때, 두 점 사이에 있는 수직선 구간의 길이 합을 빠르게 계산

하는 문제가 된다.

덮이지 않은 수직선 구간을 모으는 것은, 구간 전체의 합집합을 취하는 것과 비슷하게 하면 된다.

구간을 시작점 순으로 정렬한 후 정렬한 순서대로 본다.
지금 보고 있는 구간의 시작점이, 그 전에 등장한 모든 구간의 끝점보다 뒤에 있다면 해당 구간 사이에 빈 공간이 존재한다 (왜 그런지 생각해 보자). 이 빈 공간이 정확히 "덮이지 않은 수직선 구간" 이니 따로 저장해 둔다.

문제에서 구간을 시작점 순으로 정렬해 주니 사실 첫 번째 단계는 필요하지 않다. 하여튼 이렇게 하면, 덮이지 않은 수직선 구간들이 시작점 순으로 주어진다.

이제 두 점이 주어질 때, 두 점 사이에 있는 수직선 구간의 길이 합을 계산해야 한다. 어떠한 수직선 구간 $[l, r]$이 두 점 $x < y$ 사이에 있다는 것은 $x \le l < r \le y$ 라는 것과 동일하다. 이분 탐색을 통해 다음과 같은 두 구간을 찾는다:

$x \le l$ 을 만족하는 첫 구간 $i_1$
$y < r$ 을 만족하는 첫 구간 $i_2$ ($y \le l$ 을 만족하는 첫 구간을 찾아도 동일하다.)

이 두 구간을 찾았다면, $i_1, i_1 + 1, \ldots, i_2 - 1$ 번 구간이 $x, y$ 사이에 있음을 알 수 있다. 해당 구간들의 길이 합은, 부분 합을 전처리하여 계산할 수 있다.

G. Linear Regression

이번 대회에서 풀리지 않은 유일한 문제로, 올해를 떠나 역대 ICPC 본선에 나온 문제 중 가장 어려운 문제라고 이야기할 수 있을 것 같다. 일단 몇 가지 관찰할 수 있는 사실은 다음과 같다:

$k = 0$일 경우, 이 문제는 $N$ 개의 점을 두 개의 평행한 직선으로 감싸면서 두 직선의 세로 거리를 최소화하는 문제라고 생각할 수 있다.
Point-line duality 를 사용하면 위 문제가 점 집합 $(x_i, y_i)$ 에 대해 $min_t (max_i(x_i t - y_i) - min_i(x_i t - y_i))$ 를 계산하는 것과 동일함을 알 수 있다. 즉 $k = 0$ 일 경우 이 문제는 삼분 탐색 등으로 꽤 쉽게 해결할 수 있다.

Point-line duality 의 접근을 사용하면 이 문제는 결국 직선들이 주어졌을 때 특정 $x$ 에 대해서 $ax + b$ 의 값을 최대화하는 상위 $k$ 개의 직선을 관리하는 문제가 된다. 사실 $k \le 20$ 정도만 되어도 $O(nk^2)$ 정도에 어떻게 해볼만 할 거 같은데, $k \le 300$ 이라서 정말 꿈도 희망도 없다. 그래서 나도 확신을 가지고 이야기할 수 있는 것은 여기까지고, 이 이후부터는 전부 주워들었거나 뇌피셜이기 때문에 너무 진지하게 받아들이지는 않는 것을 권한다.

일단 문제에서 요구하는 세팅 자체는 $k$-level 이라는 이름으로 여러 가지 연구가 되어 있어 보인다. 이에 관해서 두 가지 논문을 전해들었는데, 이 중 첫번째 논문 은 내 생각에는 대충 이런 느낌인 것 같다. 다음과 같은 강화된 컨벡스 헐 트릭 자료 구조를 생각해 보자.

직선의 삽입 및 삭제 지원
주어진 $x$ 에 대해서 $ax + b$ 를 최대화하는 직선 반환 (이 때 $x$가 단조적으로 증가한다는 조건 등을 가정해야 할 수도 있다.)

논문에서는 $O(\log^2 n)$ Dynamic convex hull 자료구조를 언급하는데 아마 이런 걸 하려는 것 같다. 내가 아는 자료구조는 $x$에 대한 단조성이 보장될 때 이를 쿼리당 $O(\log^2 n \alpha (n))$ 정도에 지원할 수 있다. 구현하기 별로 어렵지 않은데, 몇 주 뒤 블로그 글로 한번 소개하게 될 것 같다.

이제 다음과 같은 방식의 라인 스위핑을 하자, $H_{in}$을 $ax + b$ 값이 상위 $K$ 개인 선분들의 자료구조, $H_{out}$ 을 그 외 선분들의 자료구조라고 하자. $H_{in}$ 은 선분 교차 알고리즘과 유사하게 BST에 관리하고, $H_{out}$ 은 강화된 컨벡스 헐 트릭 자료 구조에 관리한다.

맨 처음, $-a$ 를 최대화하는 top $K$ 개의 선분을 $H_{in}$ 에 넣고 그 외를 $H_{out}$ 에 넣자.
$H_{in}$ 에 있는 선분이 $H_{out}$ 에 있는 선분과 교차되는 첫 지점을 적절히 찾은 후, 이 지점으로 $x$ 를 옮겨주자.
교차되는 지점에서 $H_{in}, H_{out}$ 의 최대/최소를 바꿔준다.
이 과정에서 $H_{in}$ 에 있는 선분의 순서가 교차되는 건 대충 잘 처리한다.
$x$ 가 무한으로 갈 때까지 반복한다.

여기서 중요한 것은 (1) 저 적절히 가 어떻게 되는가, 그리고 (2) 교차되는 횟수가 몇번이냐이다. 내 생각에는 (1) 의 대답은 정말 적절히 되는 게 맞다고 보는데, 솔직히 나도 완전한 확신은 없다. (2) 의 질문 역시 정확히는 모르겠지만, 논문의 Theorem 1을 보면 이 횟수가 $O(n \sqrt k)$ 정도로 Bound되는 것 같다. 종합하면, 대략 $O(n \sqrt k \log^2 n)$ 정도의 시간에 $H_{in}, H_{out}$ 의 교차를 관리할 수 있고, $H_{in}$ 의 내용은 $O(n k \log n)$ 정도에 관리할 수 있으니, 아마 시간 복잡도 $O(nk \log n + n \sqrt k \log^2 n)$ 정도에 해결이 되는 것 같다. 이걸 구현할 수 있는지는 잘 모르겠다. 여담으로 저 알고리즘은 내가 논문을 보고 베껴 적은게 아니라, 원래 내가 생각한 알고리즘을 논문 보고 "비슷한거 같네" 하면서 적은거라, 논문에서 소개하는 알고리즘과 아예 다를 수도 있다.

두 번째 논문 은 simple randomized incremental 임을 주장한다. 첫 논문에 비해 이해 및 구현이 간단할 수도 있다. 사실 난 안 읽어봐서 모르겠다. 관심이 있다면 일독을 권한다.

마지막으로 이 문제와 관련이 있다고 들은 2017 중국 정보 올림피아드 문제인데, 코드가 올라와 있으니 유용한 자료인 것 같다. 맞은 사람 수를 보면 중국 올림피아드 기준으로도 정말 어려운 문제 같다.

H. Longest Substring

문자열의 모든 부분문자열에 대해서 이상한 걸 하는 문제이기 때문에, Suffix tree 비슷한 무언가를 쓰겠지 하는 마음가짐으로 시작하면 웬만하면 맞다. 문자열에 대해서 Suffix tree를 만들자. Suffix tree의 각 간선은 어떠한 suffix의 길이 $[L, R]$ 의 prefix에 대응될 것이고, 각 간선의 등장횟수는 특정 정수 $k$로 고정되어 있다. 문제를 간선에 대해서 독립적으로 생각할 경우, 결국 중요한 것은 이 간선에 대응되는 문자열 중 maximum occurrence를 최대화하면서 가능한 최대 길이가 얼마인지이다.

만약에 Suffix tree의 어떠한 간선 상에서, 길이 $x$ 가 주어질 때 $x$ 의 Disjoint occurrence를 어떻게 잘 계산할 수 있다고 하자. Maximum occurrence의 개수는 당연히 길이의 최솟값 $L$ 에서 최대화가 된다. 고로 길이 $L$ 에서의 Disjoint occurrence를 계산한 후, 이 값을 충족하는 최대 길이를 $[L, R]$ 구간에서 이분탐색 할 경우 전체 문제를 $O(n \log n)$ 번의 Disjoint occurrence 계산으로 해결할 수 있다.

중요한 것은 Suffix tree의 간선에서 Disjoint occurrence를 어떻게 계산하냐는 것이다. Suffix tree에서 각 Suffix의 맨 끝에 해당 Suffix에 대한 flag를 넣는다고 하면, 결국 어떠한 간선을 지나는 Suffix들의 집합은 해당 간선의 서브트리에 있는 flag의 집합에 대응이 된다. 대략 다음과 같은 쿼리를 관리하는 자료구조가 있다면, 서브트리에 대한 flag의 집합을 적절한 자료구조에 넣고 자료구조를 small-to-large로 관리하면 문제가 해결된다.

원소 삽입
모든 원소 간의 차이가 $L$ 이상인 최대 크기 부분집합 크기 반환.

그런데 이런 걸 log 시간 정도에 관리하는 자료구조가 있다고 보는 건 사실 꽤 비현실적이다, 두 번째 쿼리가 아주 어렵기 때문이다. 또한, 깊이가 깊어질 수록 Disjoint occurrence를 계산하는 것이 빨라진다. 정확히는, 집합의 크기가 $S$ 이고 깊이가 $L$ 일 때 Disjoint occurrence는 단순히 std::set 에서 그리디를 하는 정도로도 $min(S, N/L \log S)$ 정도의 시간에 계산 가능하다. ~~다 떠나서 서울 리저널 데이터가 강한 적이 별로 없었다.~~

고로 구태여 복잡하게 줄일 생각하지 않고, 자료구조는 std::set 으로 한 후, 단순 그리디로 Disjoint occurrence를 계산해 주면 시간 제한 안에 문제를 맞을 수 있다. 엄밀한 시간 복잡도 분석은, 깊이가 $\sqrt{N \log N}$ 미만인 노드에 대해서는 집합의 크기 합으로 시간을 쓰고, 그 이상인 노드에 대해서는 $N/L \log S$ 로 시간을 쓴다고 생각하면, 이분 탐색 포함 $(N \log N)^{1.5}$ 정도의 시간 복잡도를 증명할 수 있다. 상수까지 생각하면 문제를 여유롭게 풀 수 있는 정도이다. 로그 정도는 뗄 수 있겠지만 루트를 떼려면 아예 다른 알고리즘이 필요할 것 같다.

마지막으로 언급할 것은 Suffix tree를 어떻게 구성하는지이다. 기본적으로 Suffix tree는 Suffix array의 Cartesian tree이기 때문에, 단순히 Suffix array의 LCP를 계산한 후 스택으로 Suffix tree를 구할 수 있다. 구체적으로는 rkm0959 의 writeup을 보면 좋다. 미러의 Samsung DX 팀은 Suffix automaton을 사용했고, 구현하는데 거의 20분 정도밖에 걸리지 않았다고 한다. Suffix automaton과 Suffix array의 기능상 차이는 그렇게 많지 않아 보이는데, Suffix automaton의 인터페이스가 Suffix tree를 표현하는데 있어 더 강점이 많다는 인상을 받았다. 한국은 Suffix structure에 대한 문제가 정말 엄청나게 많이 나오는 지역이다. 이번 기회에 Suffix automaton을 배워두면 유용할 것이라고 생각한다.

I. Palindrome Type

길이 $N$ 의 문자열이 있을 때 최대 3개의 문자를 지워서 팰린드롬으로 만들 수 있는가를 판별하는 문제이다. 이 문제의 $O(N^2)$ DP 풀이는 잘 알려져 있다. 하지만 주어진 입력 범위에서는 시간 초과가 나고, 대신 최대 3개의 문자를 지운다는 제약 조건이 있다.

문자 개수가 3개 이하임을 활용하여 백트래킹을 사용하여 해결할 수 있다. $f(l, r, d)$ 을 문자열 $S[l], S[l + 1], \ldots, S[r]$ 을 $d$ 개 이하의 문자를 지워 팰린드롬으로 만들 수 있는가 판별하는 재귀 함수라고 하자. 두 가지 케이스가 있다.

$l \geq r$ 이면 참이다.
$S[l] = S[r]$ 이면 지울 필요 없으니 $f(l + 1, r - 1, d)$ 를 반환한다.
그 외 경우는 둘 중 하나를 지워보고 $d$ 를 줄인다.

위 재귀 함수는 가지가 최대 $2^3 = 8$ 개 생기고 각 가지가 최대 $O(N)$ 번 도니 $O(N)$ 시간에 종료한다.

사실 난 문제의 답이 $N - LCS(S, rev(S))$ 라는 점을 활용해서 DP로 해결하였다. LCS가 굉장히 큰 경우, DP 테이블에서 $|j - i| \le 4$ 정도인 엔트리만 관리해도 되기 때문이다. 그 외에는 아마 잘 구현된 LCS 6 를 복붙해도 풀릴 것이다.

J. Parentheses Tree

이번 대회에서 가장 쉬운 문제이다. 괄호 문자열을 앞에서부터 보면서, 닫히지 않은 열린 괄호의 개수를 관리한다. 열린 괄호에 +1, 닫힌 괄호에 -1을 더하면 된다. 리프의 깊이는 현재 닫히지 않은 열린 괄호의 개수다. 이를 모두 더해주면 된다. 시간 복잡도는 $O(N)$ 이다.

K. Shuffle Game

문제가 어렵게 쓰여 있는데, 문자열 $A, B, C$가 있을 때, A와 B를 적당히 interleave하여 $C$ 와의 LCS를 최대화하는 문제이다. $dp[i][j][k]$ 를, $A[0 \ldots i), B[0 \ldots j), C[0 \ldots k)$ 에 대한 정답이라고 하자. 상태 전이는 다음과 같다.

$A, B, C$ 에서 문자 하나를 버린다.
$A$ 의 문자를 뽑아서 $C$ 랑 매칭한다.
$B$ 의 문자를 뽑아서 $C$ 랑 매칭한다.

이를 구현하면 $O(npq)$ 시간에 문제가 해결된다. LCS를 구현하는 동적 계획법이랑 거의 동일한, 아주 전형적인 문제이다.

L. Two Choreographies

요약하면 $n$ 개의 정점과 $2n-3$ 개의 간선이 있는 그래프에서 길이가 같은 두 개의 다른 사이클을 찾는 문제이다. (사이클이 다름은 사이클을 이루는 무향 간선 집합이 다름을 뜻한다)

편의상 그래프가 연결 그래프라고 가정하자. 그래프에서 DFS를 하면 "DFS 트리" 라는 것이 나오고, 이를 통해 그래프의 간선을 Tree edge 와 Back edge 로 나눌 수 있음이 잘 알려져 있다. 문제 조건 상 Back edge는 $n - 2$ 개인데, 하나의 Back edge는 트리 상에서 사이클을 유도한다. 고로, 백 엣지가 유도하는 사이클 중 길이가 같은 것이 웬만하면 있다는 관찰을 할 수 있다. 백 엣지가 유도하는 사이클의 길이는 DFS 트리 상 두 정점의 높이 차로 쉽게 계산할 수 있으니, 여기서 길이가 같은 사이클을 찾았다면 바로 문제가 해결된다.

그렇지 않은 경우, 백 엣지로 찾은 사이클의 길이는 $3$ 이상 $n$ 사이의 서로 다른 수를 이루며, DFS 트리에 길이 $n - 1$ 의 경로가 있으니 이 트리가 직선 형태를 띈다. 이 경우에는 길이 3인 서로 다른 사이클을 직접 손으로 찾아줄 수 있는데, 다음과 같이 하면 된다:

백 엣지 하나로 찾은 길이 3의 사이클
길이 $n - 1$, $n$ 의 사이클을 만드는 백 엣지는 끝점 하나를 공유하며, 양 끝점이 트리 엣지 하나로 이어져 있다. 고로 여기서도 길이 3의 사이클이 나온다.

고로 전체 문제가 $O(n)$ 시간에 해결된다.

여담으로 그래프가 연결이 안 되어 있을 수 있다. 간선이 $2n-3$ 개 이상 이어도 풀이가 달라지지 않으니, 그냥 연결 그래프가 되도록 서로 다른 컴포넌트 간에 간선을 만들어서 이어주자. 새로 만든 간선은 모두 절선이니 사이클에 속하지 않고, 답에 영향을 주지 않는다.

문제 풀이 한 줄 요약

A: 45도 돌린 후 Grundy number를 반환값으로 하는 DP.
B: $t = 1$ 은 방향이 꺾이는 두 지점을 찾은 후, 최적해의 형태를 제약시켜서 한가지 목표 함수에 대해서만 DP. $t = 2$ 에서는 방향이 꺾이는 네 지점을 찾은 후 예외 케이스에 유의하여 단순 수식 적용.
C: 대각선을 잡고 양 옆에 있는 빈 삼각형을 세면 (오목 사각형 수) + (볼록 사각형 수) * 2 를 알 수 있음. 대각선을 잡고 빈 사각형을 이루는 점 두개를 고르면 오목 사각형의 개수를 알 수 있음. 이를 단순하게 구현하면 $n^4$ 이고 자료 구조 등으로 최적화.
D: DP를 사용하여 각 Prefix에 대한 답을 제곱 시간에 계산한 후 힙으로 최적화.
E: 간선을 정점으로 두고 multi-source Dijkstra's algorithm 구현.
F: "커버되지 않은 구간" 들의 리스트를 모은 후 이분 탐색으로 구간 내 수의 합을 계산.
G: Point-line duality를 사용하면 $n$ 개의 직선이 주어질 때 $n - k$ 개의 직선과 교차하는 최소 길이 수직 선분을 찾는 문제가 됨. 대회장에서 생각할 수 있는 수준의 간단한 풀이는 없어 보이고, 다만 $k$-level이라는 이름으로 많이 연구가 된 문제로 보임.
H: Suffix tree를 구성하면 트리의 각 에지에 대응되는 문자열의 등장 횟수가 동일하기 때문에, 여기서 $d(T)$ 를 최대화하는 최대 길이를 찾으면 됨. 길이가 고정되면 $d(T)$ 는 에지의 시작점 집합을 순회하며 계산하고, 최대 길이는 동일한 과정을 이분 탐색으로 반복. $d(T)$ 를 좀 많이 계산하는 것처럼 보이지만 이 정도로도 AC가 나옴. Suffix tree는 적절한 suffix structure로 구성.
I: 백트래킹 사용. 두 문자가 같을 때 branching할 필요가 없음을 사용하면 선형 시간에 해결 가능.
J: 단순 구현.
K: LCS와 유사하게 세 문자열의 prefix에 대한 DP.
L: Back edge가 induce하는 사이클 중 길이가 같은 것이 웬만하면 존재. 그렇지 않을 경우 삼각형 두개가 존재하며 구성 가능.

2022.12.18 problem solving (0)	2022.12.18
Segment Tree Beats와 Kinetic Segment Tree (0)	2022.12.04
Random notes on Lyndon decomposition (0)	2022.10.14
IOI 2022 Day 2 (0)	2022.08.14
IOI 2022 Day 1 (2)	2022.08.11

구사과

티스토리 뷰