2024.07.25 problem solving

ABC 127 B. Algae

주어진 점화식을 계산하면 됩니다. (답은 int32 범위도 넘어가지 않습니다.)

PA 2024. Zelki

$D[i]$ 를 (조건을 만족하는) 선물 상자 하나를 골랐고, 그 안의 사탕의 무게 합을 $m$ 으로 나눈 나머지가 $i$ 일 때, 가능한 가격 합 최소라고 정의합시다. 원래 문제와의 차이는, 원래 문제에서는 선물 상자를 여럿 고를 수 있다는 점입니다.

$D[i]$ 는 동적 계획법을 사용하여 구할 수 있습니다. $DP[x][i]$ 를, 사탕의 색상이 $x$ 이하인 사탕들만 고려하여 무게 합 나머지가 $i$ 가 되게 하는 방법이라고 합시다. $DP[x-1][_]$ 테이블이 채워져 있으면, 색상이 $x$ 인 사탕의 모든 경우를 다 시도하면서 $DP[x][_]$ 테이블을 채울 수 있습니다. $D[i] = DP[k][i]$ 입니다.

$D[i]$ 를 계산하면, 전체 문제를 Dijkstra's algorithm을 사용하여 해결할 수 있습니다. $m$ 개의 정점을 가진 그래프를 만듭시다. 이 때 $i$ $(0 \le i \le m - 1)$ 번 정점으로 가는 최단 경로는, 사탕의 총 무게를 $m$ 으로 나눈 나머지가 $i$ 인 최소 비용에 대응됩니다. $i$ 번 정점에서 $j$ 번 정점으로 움직이기 위해서는, 나머지가 $j - i$ 인 선물 상자를 하나 사야 합니다. 이 비용은 $D[j - i]$ 이고, 이미 위에서 계산한 내용입니다.

다익스트라 알고리즘은 $O(m^2)$ 에 구현할 수 있으니, 총 시간 복잡도는 $O((n + m) m)$ 입니다. 다익스트라 알고리즘을 $O(m^2 \log m)$ 에 구현할 경우 시간 초과가 날 수도 있습니다.

BOJ 32036. 수열과 쿼리 45

다양한 방법으로 해결할 수 있는 문제이지만, 내장 자료구조인 Priority Queue만을 사용하여 해결할 수 있는, 가장 구현이 간단한 버전을 소개합니다.

배열 $A$ 대신 함수 $f$ 로 두는 것이 자연스러우니 함수로 설명합시다. 문제의 목표는 $f(x) := f(x) + |x - a| + b$ 와 같은 연산에 대해서 $f$ 를 관리하는 자료구조를 구성하는 것입니다. $f$ 에 현재 일어난 업데이트가 $q$ 개라면, $f$ 는, 기울기가 $-q$ 에서 $q$ 사이 정수인 Piecewise linear function으로 표현됩니다. 또한, $f$ 는 볼록이기 때문에 각 piecewise linear function의 기울기는 $x$에 대해서 증가합니다.

이 함수 $f$ 를 다음과 같은 데이터를 사용하여 관리합시다. (Slope trick에서 관리하는 자료구조랑 동일합니다.)

• $f(x)$ 의 최솟값
• $f(x)$ 의 기울기가 $1$ 증가할때마다, 증가가 일어난 지점을 기록한 정렬된 배열 (특정 위치에서 기울기가 $n$ 증가하면, 해당 위치를 기록한 숫자가 $n$ 개 있음)

$f$ 에 업데이트가 $q$ 번 일어났다면, $f(x)$ 의 기울기가 증가하는 지점은 정확히 $2q$ 개 있을 것이고, 이 중 $q$ 번째 원소가 위치한 지점이 최솟값이 나오는 첫 지점이 됩니다.

함수 갱신 쿼리를 처리합시다. 상수항 $b$ 의 추가는 $f(x)$ 의 최솟값에 단순히 더해주는 식으로 쉽게 처리할 수 있습니다. $|x-a|$ 를 더하게 되면, 먼저 $f(x)$의 기울기가 $a$ 에서 $2$ 만큼 증가하니 정렬된 배열에 $a$ 라는 원소를 두 개 추가해 줍시다. 원래 최솟값이 있던 위치 $m$ 의 함숫값은, $|x-a|$ 가 추가되면서 함숫값이 $|m -a|$ 만큼 증가하게 됩니다. 고로 이 값만큼 최솟값을 증가시켜주는데, 함수를 갱신하면서 최솟값이 등장하는 위치가 약간 바뀌게 되므로 그 부분을 고려해 주어야 합니다.

마지막으로, 함수 $f$ 를 효율적인 자료구조로 관리해야 합니다. 최솟값은 단순 숫자이니 쉽게 관리 가능합니다. 정렬된 배열은, Running median을 관리하는 식으로 처리할 수 있습니다. 크기가 $q$ 인 max-heap과 min-heap을 따로 두어서, max-heap의 모든 원소가 min-heap의 모든 원소보다 작거나 같도록 관리해 줍니다. 모든 필요한 연산이 정렬된 배열의 중간값 정도만을 필요로 하기 때문에, 이렇게 heap 두개를 두는 것으로 전체 문제를 해결할 수 있습니다.

Ptz Winter 2017 Day5 D. Tube Master II

수들의 배정이 주어졌을 때, 만약 해가 존재한다면 이 해는 유일합니다. 고로 비용을 최소화하는 것은 함정이고, 조건을 만족하는 유일한 해를 복원하면 됩니다. 여러 가지 방법이 있지만, 가장 간단한 방법은 다음과 같습니다.

격자점을 $(0, 0)$ 에서 $(n-1, m-1)$ 까지 순서대로 탐색합시다. ($i = n, j = m$ 인 격자점은 탐색하지 않습니다.) 격자점을 기준으로 왼쪽/위 로 뻗어나가는 선의 선택 여부를 결정하면, 오른쪽/아래 로 뻗어나가는 선의 선택 여부를 결정할 수 있습니다. $(i, j)$ 와 $(i, j+1)$ 을 잇는 가로선을 선택했다는 것을 $H_{i, j}$, $(i, j)$ 와 $(i+1, j)$ 를 잇는 세로선을 선택했다는 것을 $V_{i, j}$ 로 표기합시다. 그렇다면 격자점 $(i, j)$ 에서 인접한 4개의 선은

• 왼쪽: $H_{i, j-1}$
• 오른쪽: $H_{i, j}$
• 위쪽: $V_{i-1, j}$
• 아래쪽: $V_{i, j}$

이 때 $i < 0, j < 0$ 일 경우 $H_{i, j} = V_{i, j} = 0$ 입니다. 이제 $H_{i, j-1}, V_{i-1, j}$ 가 결정되었을 때 $H_{i, j}, V_{i, j}$ 를 다음과 같이 결정할 수 있습니다.

• $H_{i, j-1} + V_{i-1, j} = 2$ 일 경우 $H_{i, j} = V_{i, j} = 0$ (인접한 선이 최대 2개)
• $H_{i, j-1} + V_{i-1, j} = 1$ 일 경우 $H_{i, j} = 1$ 혹은 $V_{i, j} = 1$ (인접한 선이 2개여야 하고, 두 인접한 가로/세로선을 같이 사용하면 안 됨에 주의)
• $H_{i, j-1} + V_{i-1, j} = 0$ 일 경우, $H_{i, j} = V_{i, j}$ 여야 한다. 고로:
  • $c_{i, j} = 0$ 일 경우 $H_{i, j} = V_{i, j} = 0$
  • $c_{i, j} = 1$ 일 경우 $H_{i, j} = V_{i, j} = 0$
  • $c_{i, j} = 3$ 일 경우 $H_{i, j} = V_{i, j} = 1$
  • $c_{i, j} = 4$ 일 경우 $H_{i, j} = V_{i, j} = 1$
  • $c_{i, j} = 2$ 일 경우:
    • $H_{i, j} = V_{i, j} = 1$ 인 경우 $V_{i-1, j+1}$ 이 참이어야 루프가 셀을 빠져나올 수 있다.
    • 반대로 $V_{i-1, j+1}$ 이 참일 경우 $V_{i, j+1}$ 이 거짓이어야 하기 때문에 $H_{i, j} = V_{i, j} = 1$ 이 된다.
    • 고로 필요충분조건이 되고, 계산 순서에 따라 $V_{i-1, j+1}$ 이 이미 계산되기 때문에 유일하게 결정 가능하다.

이런 식으로 모든 가로/세로 선의 답을 결정하면 $H_{i, m}, V_{n, j}$ 를 구하는 것은 쉽습니다. 다만 저렇게 찾은 구성이 무조건 문제 조건을 만족하는 것은 아닐 수 있기 때문에, 조건을 만족하는 지 체크한 후 답을 출력해야 합니다. 시간 복잡도는 $O(nm)$ 입니다.

PA 2024. Kolorowy las

Solution outside of syllabus. 쿼리를 역순으로 처리합시다. 만약 4번 쿼리가 들어오면 응답하지 않고 단순히 트리에 마킹해 둡니다. 3번 쿼리가 들어오면, 해당 정점에서 거리가 $d$ 이하인 모든 쿼리들을 색칠하고 마킹에서 지워주면 됩니다. 결국 간선 추가/제거, 정점 업데이트, 특정 정점에서 가장 가까운 마킹된 정점을 찾는 연산을 지원하는 자료구조가 필요하고, 이는 Top tree를 사용하면 쉽게 할 수 있습니다.

Solution inside of syllabus. Offline dynamic connectivity와 유사하게 각 3번 쿼리를 단위 시간으로 두고, 간선 추가/제거를 "특정 구간에 간선 $(u, v)$ 추가" 와 같이 변환합시다.

목표는 세그먼트 트리를 만드는 것입니다. 시간 구간 $[l, r]$ 에 대응되는 노드가 저장하는 정보는 다음과 같습니다: 모든 정점 $v$ 에 대해, $[l, r]$ 에 있는 3번 쿼리만이 처리되었다고 합시다. 이 때, 쿼리가 처리되는 시점에 $v$ 를 도달할 수 있는 모든 3번 쿼리 $(u, r)$ 에 대해서, $r - dist(u, v)$ 의 최댓값을 저장합니다.

만약에 위와 같은 세그먼트 트리를 구성할 수 있다면, 4번 쿼리는 이 세그먼트 트리를 통해서 응답할 수 있습니다. 단순히 이분 탐색을 한다면 $O(\log^2 q)$ 시간이 들겠지만, 트리를 타고 내려가면 $O(\log q)$ 시간에 가능합니다.

세그먼트 트리를 $O(nq)$ 시간/공간 복잡도에 구성하는 것은 간단합니다. 리프 노드에 대해서 해당 시점에 존재하는 간선들로 트리를 만들고, 이 트리에서의 거리로 정보를 채웁니다. 리프 노드가 아닌 경우, 왼쪽/오른쪽 자식에서 단순히 최댓값을 구하면 됩니다.

물론 이것으로는 느리니, 각 노드에 $n$ 개의 정보를 저장하는 대신 이보다 적은 정보를 저장하는 식으로 트리의 노드를 압축 해 봅시다. 노드 $[l, r]$ 에서 중요한 정점 을 다음 정점들로 정의합니다:

• $[l, r]$ 에서 색칠될 노드
• $(l, r)$ 구간에서 존재 여부가 바뀔 간선들의 양 끝점

모든 중요한 정점의 개수 합은 $O(q \log q)$ 개이며, 고로 압축된 트리의 크기 합도 $O(q \log q)$ 입니다.

노드 $[l,r]$ 에서 전체 트리를 가지고 다니는 대신, 중요한 정점 으로만 이루어진 트리 압축을 구성합시다. 트리 압축은, 압축을 해제할 수만 있으면 올바릅니다. 다시 말해, 압축 후 그래프의 모든 노드에 $r - dist(u, v)$ 의 최댓값을 저장한 것을 토대로, 압축 전 그래프의 모든 노드에 $r - dist(u, v)$ 의 최댓값을 역산할 수 있으면 됩니다. 압축 후의 그래프는 degree 1인 정점들을 반복해서 지우고, 여러 degree 2인 정점들을 하나의 긴 간선으로 대체하는 식으로 구성됩니다. 지워진 degree 2 정점들은, 대체된 긴 간선의 양쪽 끝을 보고, 거기에 적힌 $r - dist(u, v)$ 의 최댓값을 토대로 답을 역산할 수 있습니다. 지워진 degree 1 정점은, 지움 체인을 반복해서 올라가다 보면, degree 2 정점 혹은 트리 압축에 존재하는 정점에 도달하게 됩니다. 거기에 적힌 $r - dist(u, v)$ 의 최댓값을 토대로 답을 역산할 수 있습니다.

트리를 압축 / 압축 해제하는 방법을 찾았으니 이제 구체적인 세그먼트 트리 구성 방법을 생각해 봅시다. 리프 노드에서 중요한 정점 은 단 하나입니다. 고로 트리 압축은 자명합니다. 그냥 색칠하는 정점에 $r$ 을 적으면 됩니다. 리프 노드가 아니면, 해당 구간을 덮는 간선들을 모두 트리에 추가한 후 압축하고, 양 자식에 대해 세그먼트 트리를 구성합니다. 자식의 세그먼트 트리가 구성되면, 자식의 $r - dist(u, v)$ 최댓값을 모은 후 압축을 해제해서 부모의 노드를 구성합니다. 이를 모두 구현하면, $O(q \log q)$ 시간에 세그먼트 트리를 구성할 수 있고, 4번 쿼리는 위에서 설명한 것과 동일하게 처리할 수 있습니다.

ABC 127 D. Integer Cards

관찰 1: 한번 색칠한 원소를 다시 색칠할 필요는 없습니다. 두 번 이상 색칠되었다면 그 중 값이 작았던 색칠은 무시해도 됩니다.
관찰 2: $k$ 개 이하의 원소를 골라 $v$ 로 색칠하는 것은 $1$ 개의 원소를 골라 $v$ 로 색칠하는 기회가 $k$ 번 있는 것과 동일합니다. 고로 색칠을 여러 원소가 아니라 하나의 원소에만 한다고 생각할 수 있습니다. (실제 $k$ 개의 원소를 만들어서 처리하는 것은 아닙니다.)
관찰 3: 초기 $n$ 개의 원소가 주어진다고 생각하는 대신, 초기 배열은 모두 $0$ 으로 차 있고 $1$ 개의 원소를 $a_i$ 로 바꿀 수 있는 기회가 주어진다고 생각해도 됩니다. (이 기회들을 모두 사용할 경우 어차피 입력과 동일한 상태에 도달합니다. 이 기회 중 일부를 사용하지 않았더라도 이 곳에는 다른 원소가 색칠될 것이고 그 색칠된 원소는 원래 원소보다 큰 것일 겁니다.)
관찰 4: 모든 색칠 기회 중 값이 가장 큰 $n$ 개의 색칠을 선택해서 서로 다른 원소에 색칠하는 것이 최적입니다.

고로 입력을 값 순으로 정렬한 후 가장 큰 $n$ 개를 합하면 됩니다.

BOJ 15933. 행렬 곱셈

행렬 $a \times b$ 와 $b \times c$ 를 $a \times c$ 로 대체하는 연산을 반복해서 최종적으로 행렬 $u \times v$ 를 만들었다고 합시다. 이 수열에 적용한 연산을 거꾸로 풀어 보면, 초기 수열은 $u \times p_1, p_1 \times p_2, \ldots, p_k \times v$ 의 형태임을 알 수 있습니다. $a \times b$ 행렬을 $a \rightarrow b$ 로 가는 단방향 간선이라고 생각하면, 결국 문제는 그래프의 모든 간선을 지나는 경로가 존재하는지를 찾는 문제가 되고, 그러한 경로가 여럿 있다면 그 중 $u \times v$ 의 최댓값을 출력하는 문제가 됩니다. 그래프의 모든 간선을 지나는 경로는 오일러 경로라고 하며, 이것이 존재하기 위해서는

• degree 0인 정점을 모두 지우고 모든 간선을 무방향 간선으로 봤을 때, 그래프가 연결되어야 함.
• 둘 중 하나가 만족해야함:
  • 모든 정점의 indegree와 outdegree가 같음.
  • indegree = outdegree + 1인 정점이 정확히 하나, indegree + 1 = outdegree인 정점이 정확히 하나 있으며, 그 외 모든 정점의 indegree와 outdegree가 같음.

입력을 그래프로 처리하고 모든 degree 0 정점을 지웁시다. 만약 위 조건을 만족하지 않으면 $0$ 을 출력합니다. 조건을 만족하며 모든 정점의 indegree와 outdegree가 같다면, 그래프는 오일러 회로를 가집니다. 고로 임의의 정점에서 출발해서 그 정점에서 끝나는 오일러 경로가 존재하니, 지워지지 않은 최대 번호 정점의 번호 제곱을 출력하면 됩니다. 그렇지 않다면, 그래프는 오일러 경로를 가지며, 이 경로는 항상 indegree + 1 = outdegree인 정점에서 출발하고 indegree = outdegree + 1인 정점에 도착합니다. 두 정점을 찾아서 번호 곱을 출력합니다.

고로 하나의 $i$ 에 대해서 $O(n)$ 에 해결 가능합니다. 이를 모든 $i$ 에 대해 반복하면 전체 시간 복잡도는 $O(n^2)$ 가 됩니다. (자료구조 구현을 조금 더 하면 $O(n)$ 으로 최적화 할 수도 있습니다.)

BOJ 17278. 이진 문자열

연산을 처리하는 방식을 거꾸로 뒤집어서 계산하면 $O(km)$ 에 문제를 해결할 수 있습니다. 모든 $1 \le i \le k$ 에 대해서 $i$ 번 문자의 답을 각각 구합시다. 연산을 역순으로 처리합니다. 만약에 $i$ 가 $[y+1, 2y-x+1]$ 구간에 들어간다면, 이 문자는 그 전 쿼리에서 $i - (y-x+1)$ 번 문자였던 것을 뒤집은 문자와 동일합니다. $i \geq 2y - x + 2$ 인 경우에는 그 전 연산에서 $i - (y - x + 1)$ 번 문자입니다. 이러한 식으로 현재 답을 구하고자 하는 문자가 특정 연산에서 어떤 문자였는지를 따라가다보면 초기 상태의 문자열에 도달하게 되며, 답을 구할 수 있습니다.

위와 같은 해결 방법에서, 각 문자의 답을 구하는 것을 묶어서 처리하면 계산을 효율화할 수 있습니다. 현재 문자열의 $i$ 번 문자가 최종 문자열의 $A[i]$ 번 문자에 대응된다는 의미의 배열 $A$ 를 만듭시다. 최종 문자열을 초기 문자열로 바꾸는 식으로 역순으로 처리하니, 초기 배열의 값은 $A = [1,2, \ldots, k]$ 입니다. 매 연산에서 우리는, 배열의 $[y+1, 2y-x+1]$ 번째 원소들이 $[x, y]$ 번째 원소를 뒤집은 것에 대응되며, 그 오른쪽의 원소들은 그 위치가 $y-x+1$ 만큼 왼쪽으로 이동함을 알 수 있습니다. 모든 $i \in [y+1, 2y-x+1]$ 번째 원소들에 대해서, 최종 문자열의 $A[i]$ 번 문자가 $A[i - (y-x+1)]$ 번 문자를 뒤집은 것과 동일하다고 표시해 두고, 이 원소들을 지워줍시다. 모든 연산을 진행하면, 최종적으로 각 문자는 초기 문자열의 특정 문자에 대응되거나, 아니면 특정 문자를 뒤집은 것에 대응됩니다. 이 정보는 문자열을 왼쪽에서 오른쪽으로 순서대로 복구하면서 모두 얻을 수 있씁니다.

위 연산들은 모두 Fenwick tree를 통해서 해결할 수 있습니다. Fenwick tree를 사용하면 $k$ 번째 원소를 $O(\log n)$ 에 찾을 수 있기 때문입니다.

BOJ 32037. 아인타, 빈타, 그리고 씬타

수열 $(A, B)$ 에 연산을 수행해서 어떤 집합 $S$ 를 만들 수 있다고, 꼭 $S$ 의 부분 집합을 만들 수 있는 것은 아닙니다. 예를 들어 공집합은 만들 수 없으니, 당연한 이야기입니다. "정확히 $k$" 인 문제를 "$k$ 이하" 로 변환하듯이, $S$ 를 만들 수 있으면 부분 집합도 만들 수 있게끔 문제를 변형합시다. 예를 들어서, Ainta가 $B_i$ 를 $A_i$ 로 교환할 수 있을 뿐만 아니라, $B_i$ 를 아예 지워버릴 수도 있다고 합시다. 이렇게 변환하게 되면, 원래 문제보다 해집합이 더 커지게 됩니다. 즉, 원래 문제의 해는 변환된 문제에서도 해가 되지만, 모든 변환된 문제의 해가 원래 문제의 해가 되지는 않습니다.

변환된 문제는 네트워크 플로우로 해결할 수 있습니다. 다음과 같이 그래프를 만듭시다. ($S$ 는 source, $T$ 는 sink, 모든 간선 가중치는 1)

• 모든 $1 \le i \le n$ 에 대해 $S \rightarrow (i, 0)$
• 모든 $1 \le i \le n$ 에 대해 $(i, 0) \rightarrow (A[i], 0), (i, 0) \rightarrow (B[i], 0)$
• 모든 $1 \le i \le 10,000$ 에 대해 $(i, 0) \rightarrow (i, 1)$
• 모든 $1 \le i \le n$ 에 대해 $(A[i], 1) \rightarrow (i, 1), (C[i], 1) \rightarrow (i, 1)$
• 모든 $1 \le i \le n$ 에 대해 $(i, 1) \rightarrow T$

이 그래프의 최대 유량이 문제의 정답이 되며, 이 때의 해는 모든 선택된 $(i, 0) \rightarrow (i, 1)$ 간선임을 알 수 있습니다.

만약에 모든 ${A[i], B[i]}$ 와 ${A[i], C[i]}$ 에 대해서 하나 이상의 숫자가 해에 선택되었다면, 원래 문제에서도 해를 항상 만들 수 있습니다. 공집합을 만드는 대신 그 숫자를 고르면 되기 때문입니다. 하지만 만약 ${A[i], B[i]}$ (혹은 $C[i]$) 가 모두 선택되지 않았다면, 그 경우에는 원래 문제에서의 해가 되지 않습니다. 이러한 경우를 나쁜 경우라고 하고, 그러한 두 숫자 쌍을 나쁜 쌍 이라고 합시다. 다음과 같은 사실이 성립합니다:

Lemma. 나쁜 쌍 이 존재하지 않는 해에 shortest augmenting path를 흘려서 얻은 새로운 해는, 역시 나쁜 쌍 을 가지지 않는다.
Proof. 모순을 가정하자. 일반성을 잃지 않고 새로운 나쁜 쌍 이 ${A[i], B[i]}$ 의 형태라고 하자. Augmenting path를 흘려줌으로써, 원래 ${A[i], B[i]}$ 중 하나 이상이 선택되어 있던 해가 그렇지 않게 변형되었다. 원래는 $B[i]$ 만 선택되어 있었는데 그렇지 않게 되었다고 가정하자. Augmenting path는 $(j, 1) \rightarrow (B[i], 1) \rightarrow (B[i], 0)$ 을 거쳐 ($B[i] \in {A[j], C[j]}$) sink를 향한다. 이 경로를 $S \rightarrow (i, 0) \rightarrow (B[i], 0)$ 로 대체할 수 있다. 일단 경로의 길이가 strictly 감소하며, 두 간선의 잔여 용량이 무조건 있기 때문이다 ($S \rightarrow (i, 0)$ 은 역변에 의해 취소될 수 없는 간선이고, $S \rightarrow (i, 0)$ 에 용량이 없으면 $(i, 0) \rightarrow (B[i], 0)$ 에도 용량이 없다). 고로 shortest 가정에 모순이다. 이 Augmenting path에서 처음 등장한 것이 ${A[i], B[i]}$ 중 $B[i]$ 라고 가정하는 식으로 생각하면, 원래 해에 $B[i]$ 만 선택되어 있었다는 가정은 일반성을 잃지 않음을 볼 수 있다. $\blacksquare$

나쁜 쌍 이 존재하지 않는 해는, $A[i]$ 를 모두 고르는 방식으로 쉽게 구할 수 있습니다. 유량 네트워크에 미리 이 해를 설정해 놓고, shortest augmenting path를 반복적으로 구해줍시다. 이렇게 얻은 해는 Lemma에 의해 올바른 해이고, 이 해보다 큰 해는 존재할 수 없습니다. Augmenting path가 없는 그래프는 최대 유량을 가지며, 최대 유량은 변형된 문제의 최적해의 크기와 같기 때문입니다. 변형된 문제의 해집합이 더 크니, 변형된 문제보다 더 큰 $k$ 를 가질 수가 없습니다. (고로, 이 알고리즘은 변형된 문제의 최적해 크기와 원래 문제의 최적해 크기가 같다는 증명이 됩니다. 한편, 변형된 문제의 임의의 최적해가 항상 원래 문제의 최적해가 되지는 않습니다.)

Shortest augmenting path를 naive하게 구하면 $O(n^2)$ 로, 시간 안에 문제를 풀 수 있습니다. 이 방법을 Edmonds-Karp algorithm이라고 하며, Syllabus에 포함된 플로우 알고리즘입니다. Syllabus에 포함되어 있지 않은 Dinic's algorithm을 사용해도 shortest augmenting path를 반복적으로 구하며, 이 때의 시간 복잡도는 $O(n^{1.5})$ 입니다.

BOJ 19068. Sequence

Persistent BBST의 구현을 연습하는 문제입니다. 저의 풀이는 이 글 에 나와 있는 Weight-Balanced Tree를 사용하며, 다음과 같이 각 연산을 구현합니다:

• 1번 연산은 BBST를 따라 내려가며 구간 쿼리를 하면 됩니다. 세그먼트 트리와 동일하고 쉽습니다.
• 3번 연산은 1번 연산과 비슷합니다. $A^\prime$ 에 대해서 구간 쿼리와 Merge 연산을 통해서 $A^\prime[l, r]$ 에 대응되는 새로운 BBST를 $O(\log n)$ 시간에 구성합니다. 이후 split/merge를 통해서 $A$ 에 해당 BBST를 끼워넣으면 됩니다.
• 2번 연산에서는 먼저 $r - l + 1$ 이 $k$ 의 배수임을 가정합시다. $[l-k, l-1]$ 구간을 $(r-l+1)/k$ 개 복사한 BBST를 얻어야 합니다. $[l-k, l-1]$ 구간에 대응되는 BBST를 구간 쿼리를 통해 $O(\log n)$ 시간에 얻고, exponentiation by squaring을 통해서 이 구간을 $(r-l+1)/k$ 개 복사합시다 ($T$ 라는 BBST를 두개로 복사하는 것은, 그냥 $(T, T)$ 를 자식으로 가지는 트리 하나를 만드는 것과 동일하다는 관찰에서 착안합니다). 이렇게 하면 $l$ 에서 시작하는 $k$ 의 배수 길이 구간은 채울 수 있고, 남는 나머지는 대응되는 위치에서 split/merge 해서 끼워넣으면 됩니다.

관련 있을 수도 있는 글들

• 2023.12.05 problem solving
• 2023.08.29 problem solving
• 구간 최장 증가 부분 수열 쿼리 (Part 2)
• 구간 최장 증가 부분 수열 쿼리 (Part 1)
• 2022.12.18 problem solving
• 2022.07.17 problem solving
• 2021.12.02 problem solving
• 2021.07.27 problem solving
• Klein's Algorithm for Computing Edit Distance on Tree
• CCO 2019 Shopping Plans
• 2021.01.17 problem solving
• 2020.08.14 problem solving
• 2020.08.09 problem solving
• 2019.12.26 problem solving