koosaga's profile image

koosaga

November 22, 2022 00:00

2022 ICPC Seoul Regional

algorithm , icpc , competitive-programming

2022 ICPC Seoul Regional

ICPC 서울 리저널 측이 공식 풀이를 제공하지 않아서 2020년부터 ICPC 리저널의 비공식 풀이를 작성하고 있다. 이번에도 그 때와 같이 2022 ICPC Seoul Regional의 문제를 풀어보는 시간을 가진다. 올해 문제의 난이도는 작년과 유사한 수준으로 꽤 어려운 편에 속한다. 체감상은 작년보다도 약간 더 어려운 느낌인데, 스코어보드로는 그렇게 보이지 않는다는 점에서 참가 팀의 수준이 높아졌다고 느꼈다.

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

문제 풀이 한 줄 요약

  • 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하는 사이클 중 길이가 같은 것이 웬만하면 존재. 그렇지 않을 경우 삼각형 두개가 존재하며 구성 가능.

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)$ 번의 이분 탐색으로 해결할 수 있다.

중요한 것은 Suffix tree의 간선에서 Disjoint occurrence를 어떻게 계산하냐는 것이다. Suffix tree에서 각 Suffix의 맨 끝에 해당 Suffix에 대한 flag를 넣는다고 하면, 결국 어떠한 간선을 지나는 Suffix들의 집합은 해당 간선의 서브트리에 있는 flag의 집합에 대응이 된다. 서브트리에 대한 flag의 집합을 적절한 자료구조에 넣고 자료구조를 small-to-large로 관리한 후, Disjoint occurrence를 빠르게 세어 줄 수 있으면 된다. 여기서 Disjoint occurrence에 대해서 몇 가지 관찰할 수 있는 사실이 있는데:

  • 깊이가 깊어질 수록 Disjoint occurrence를 계산하는 것이 빨라진다. 정확히는, 집합의 크기가 $S$ 이고 깊이가 $L$ 일 때 Disjoint occurrence는 단순히 std::set 에서 그리디를 하는 정도로도 $min(S, N/L \log S)$ 정도의 시간에 계산 가능하다.
  • 꽤 어려운 문제이기 때문에 log 정도 시간에 자료구조를 통해서 관리하는 것이 비현실적이다. sqrt로 할 거면 나이브가 더 빠르다고 보는게 맞다.
  • 서울 리저널 데이터가 강한 적이 별로 없었다.

고로 구태여 복잡하게 줄일 생각하지 않고, 자료구조는 std::set 으로 한 후, 단순 그리디로 Disjoint occurrence를 계산해 주면 시간 제한 안에 문제를 맞을 수 있다.

마지막으로 언급할 것은 Suffix tree를 어떻게 구성하는지이다. 기본적으로 Suffix tree는 Suffix array의 Cartesian tree이기 때문에, 단순히 Suffix array의 LCP를 계산한 후 스택으로 Suffix tree를 구하는 것도 크게 복잡하지 않다. 그 외에는 Suffix automaton을 사용할 경우 Suffix tree를 꽤 쉽게 얻을 수 있다. 이 문제 기준으로는 어느 쪽을 사용하든 크게 차이가 없어 보이는데, Suffix automaton이 Suffix tree에 비해서 훨씬 더 확장성이 있고 편한 인터페이스를 가지고 있다고 생각한다. SCPC와 같이 한국 대회에서는 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$ 개 이상 이어도 풀이가 달라지지 않으니, 그냥 연결 그래프가 되도록 서로 다른 컴포넌트 간에 간선을 만들어서 이어주자. 새로 만든 간선은 모두 절선이니 사이클에 속하지 않고, 답에 영향을 주지 않는다.