2019.12.26 problem solving

GCJ 2008 World Finals A. Juice

사과와 바나나 주스의 비율로 가능한 후보는 $N^2$ 개입니다. 단순히 생각하면 $10000^2$개이지만, 사과의 비율을 $i$번째 사람을 만족시키는 최소 비율로 하고, 바나나 주스의 비율을 $j$번째 사람을 만족시키는 최소 비율로 하여도 문제가 없기 때문입니다. 사과, 바나나 주스의 비율을 고정하면 당근 주스의 비율이 $10000-A-B$와 같이 자동적으로 정해집니다.

사용할 사과 주스의 비율 $A$를 고정시킵시다. 이제 각각의 사람을 순서대로 고려합니다. 만약에 어떤 사람이 원하는 사과 주스의 비율이 $A$를 초과하면 무시해 줍니다. 그렇지 않은 경우, 이 사람이 원하는 바나나/당근 주스의 비율이 $B, C$ 라고 하면 $B_i \le B, C_i \le C = 10000 - A - B$를 만족합니다. 적당히 이항하면 $B_i \le B \le 10000-A-C_i$ 여야지 이 사람이 원하는 비율이 나옴을 알 수 있습니다. 고로 위와 같은 구간이 최대로 겹치는 개수를 출력하면 됩니다. 구간의 끝점 크기가 작기 때문에, 변홧값 배열을 사용하여 해결할 수 있습니다. 구간이 시작하는 시점 $B_i$에 구간 하나가 시작했다고 카운터를 증가시키고, $10000-A-C_i$ 에는 구간 하나가 감소했다고 카운터를 감소시킵시다. 이제 0부터 10000까지 순서대로 현재까지 읽은 카운터의 합을 계산한 후, 이 합의 최댓값을 계산하면 됩니다. 사과 주스 하나에 대해 $O(10000 + N)$ 시간이 소모되었으니 시간 복잡도는 $O(N^2 + 10000N)$ 입니다.

AGC 037 C

문제의 연산을 뒤집어서, $B$ 에 역연산을 적용해서 $A$ 를 만드는 것으로 변형해 봅시다. 이 경우 한 연산은 B[i] -= B[i-1] + B[i+1]; 을 적용하는 것이라고 볼 수 있습니다. 이렇게 되면 다음과 같은 관찰을 할 수 있습니다.

• 어떠한 $i$ 에 연산을 적용할 수 있다면, $i-1, i+1$ 에는 연산을 적용할 수 없다.

고로, 연산을 할 수 있는 상황에서는 무조건 연산을 하면 됩니다. 그 위치에 연산을 하지 않으면, 그 위치에 값을 바꿀 가능성이 있는 다른 값들 역시 연산을 적용할 수 없기 때문에, 양 옆에 있는 값이 고정이라고 생각하면 연산을 미룰 이유가 없습니다. 또한, 선택의 여지가 생기지 않기 때문에 최소화 역시 의미 없고, 단순히 답이 존재하는지, 그리고 그 때의 연산 횟수가 얼마인지만 알면 됩니다. 여기까지의 관찰을 하면 $O(\sum B)$ 정도 시간에 시뮬레이션을 하면 되지만 물론 느립니다.

어떠한 $i$ 에 연산을 꼭 한번만 할 필요는 없고, $B_i \geq A_i$ 를 만족하는 선에서 최대한 많이 $B_{i-1} + B_{i+1}$ 을 빼도 크게 상관이 없습니다. 이 경우 연산 횟수는 $\frac{B_i - A_i}{B_{i-1} + B_{i + 1}}$ 정도로 예측할 수 있고, 이 횟수만큼 $B_i$ 에서 빼는 식으로 구현할 수 있습니다. 이러한 연산을 묶인 연산 이라고 정의합시다. 이 때, 우리가 $B$ 를 $A$ 로 만들기 위해서 시행하는 묶인 연산은 많아야 $O(N \log B)$ 정도가 됩니다. 한번의 묶인 연산은 $C_i = B_i - A_i$ 를 $B_{i-1} + B_{i+1}$ 로 나눈 나머지 로 대체하는 것과 동일하고, 나머지 연산을 수행하면 어떠한 수의 크기가 반 이하로 줄기 때문입니다.

고로, 묶인 연산을 반복해 주는 것으로 문제를 해결할 수 있습니다. 이러한 위치들을 Queue로 관리하면 묶인 연산을 할 수 있는 위치를 빠르게 알 수 있고 전체 문제가 해결됩니다.

IOI 2017 Practice. Mountains

$dp[L][R] = $ ($[L, R]$ 구간에 있는 점들을 사용하여 찾을 수 있는 최적해의 크기) 라고 정의합시다. 두 가지 경우가 있습니다.

• $L$ 번 점을 선택하지 않은 경우. 답은 $dp[L+1][R]$ 이 됩니다.
• $L$ 번 점을 선택한 경우. $L$ 번 점을 볼 수 있는 점들은 모두 더 이상 선택할 수 없고, 볼 수 없는 점들만 선택할 수 있게 됩니다. 볼 수 있는지 없는지 여부는 L에서 R 방향으로 스캔하면서, "현재 본 점 기준 시선이 가장 높이 올라가는 점" 을 관리하면 알 수 있습니다. 볼 수 없는 연속한 점들은 여러 개의 구간으로 표현할 수 있습니다. 각 구간에 대해서 따로 처리하여도, 그 사이에 구간을 끊는 구실을 한 점들이 각 구간 사이의 시선을 막기 때문에, 각각의 최적해를 그대로 합쳐도 문제가 되지 않습니다.

이렇게 하면 $O(N^3)$ 풀이를 찾을 수 있습니다.

$O(N^2)$ 풀이를 관찰하는 방법 중 하나는, 이 $O(N^3)$ 점화식에서 $dp[L][R]$ 을 채우는 점화관계와 $dp[L][R+1]$ 을 채우는 점화관계가 큰 차이가 없다는 것을 보시면 됩니다. 두 점화관계가 다른 값을 채우는 지점은 둘이 참고하는 "마지막 구간" 에서만 차이가 생깁니다. 마지막 구간의 시작점은, L에서 R 방향으로 시작하였을 때 시선이 가장 높이 올라간 점의 다음 점이 됩니다. 이 점을 $f(L, R)$ 이라고 하고 이 위치를 기준으로 관찰해 봅시다.

$L$ 번 점을 선택하였다면, $f(L, R)$ 점은 절대 선택할 수 없고, $L$과 $f(L, R)$ 을 잇는 선을 그어보면, 이 점을 선택하지 않은 이후 생긴 두 부분에서 문제가 독립적이고, 두 부분의 최적해를 합쳐줄 수 있다는 것을 알 수 있습니다. 고로 $L$ 번 점을 선택하지 않은 경우 답은 $dp[L][f(L, R) - 1] + dp[f(L, R) + 1][R]$ 이 됩니다. $f(L, R)$ 을 전처리 하는 데 $O(N^2)$, DP 계산에 $O(N^2)$ 로 시간 복잡도는 $O(N^2)$ 입니다.

AGC 037 F

문제의 조건을 만족하는 배열 전체 개수를 세어야 하니, 단순한 접근은 모든 부분배열을 순회한 후 이 부분배열이 문제 조건을 만족하는지 확인해 보는 것입니다. 고로, $i = 1, j = N$ 이라고 생각하고 전체 배열에 대해 문제를 해결하는 방법을 고민해 봅시다. 랭크의 정의가 $k$ 라는 값에 대해서 귀납적으로 정의되어 있으니 작은 숫자부터 큰 숫자로 올라가면서 문제를 해결하는 것이 적절할 것입니다.

배열 $A$ 의 모든 수가 같다면, 이 배열이 문제 조건을 만족하기 위해서는 숫자의 개수가 1개이거나 $L$ 개 이상이어야 합니다. 이 상태에서는 답을 판단하기 쉬우니 이 상태에 도달하도록 문제의 크기를 줄여나갑시다.

어떠한 배열의 최솟값 $m$이 등장하는 위치가 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ 와 같은 구간이라고 합시다. 이 때 이 구간은 최대한 크게 잡혀있어서 ($r_i + 1 < l_{i+1}$ 을 만족하여 더 이상 적은 개수의 구간으로 표현할 수 없는, 짧게 이야기 하면 극대(maximal) 구간) 위 구간 안에 있는 원소들은 $m+1$ 로 합칠 수 있다고 합시다. 이 때 구간의 길이가 $L$ 미만인 것이 있다면 이 배열은 문제 조건을 만족하지 않습니다. 절대 해당 구간을 하나로 합칠 수 없기 때문입니다. 그렇지 않다면 길이 $l$ 의 구간은 1에서 $\frac{l}{L}$ 사이의 길이를 가지는 $m+1$ 구간으로 변환 가능합니다. 최종적으로 수를 합칠 때 숫자의 개수가 1인 상태로 문제의 조건을 만족하는 경우는 예외적인 상황을 제외하면 없습니다. 고로 구간은 최대한 길게 유지하는 것이 좋으니, $\frac{l}{L}$ 의 구간으로 변환해놓은 후 다음 최솟값으로 진행하면 됩니다. 이를 반복하여 모든 수가 같은 상황까지 도달한 후 기저 조건을 만족하는지 체크하면 됩니다.

이를 그대로 구현하면 $O(n^2)$, 자료구조를 사용하면 $O(n\log n)$ 정도의 시간이 소모됩니다. 하지만 이러한 류의 알고리즘은 Stack을 사용하면 효율적으로 구현할 수 있는 경우가 많습니다. 여기서는 위 알고리즘을 Stack을 사용하여 $O(n)$ 에 구현하는 방법을 소개합니다. $[1, i - 1]$ 에서 계산한 결과를 $[1, i]$ 로 바꾸기 위해서, 오른쪽에 있는 원소들은 추가적으로 들어오는 변형에 민감해야 합니다. 고로 위와 같은 프로시저를 똑같이 하는데, 배열의 끝에 닿아있는 원소에 대해서는 합치는 연산을 하지 않은 표현을 생각해 봅시다. 이렇게 될 경우, 단조감소하는 형태의 배열을 관리할 수 있고, 이를 Stack에 저장할 수 있습니다. 새로운 원소 $x$가 오른쪽에 들어오면, Stack 상에서 $x$ 보다 작은 원소를 위에서 설명한 방법대로 순차적으로 합쳐주고, $x$ 를 오른쪽에 끼워넣을 수 있습니다. 이러한 식으로 구현한 후, $[1, N]$ 까지 연산이 끝났을 경우 오른쪽부터 순차적으로 원소들을 합쳐준 후 기저 조건을 확인하면 됩니다.

Stack을 사용한 방법의 장점은 각 prefix $[1, i]$ 에 대해서 관리하기 좋은 표현을 저장한다는 점입니다. 고로, 이 접근을 일반화하여서 전체 문제를 해결하는 것을 시도할 수 있습니다. 각 $i$ 에 대해서 이에 대응되는 시작점의 개수를 가지고 있어야 하는데, 구간의 길이를 $\frac{l}{L}$ 로 변환하는 과정에서 시작점으로 가능한 후보들이 날아가는 문제가 생깁니다. 고로 각 원소에 대해서 숫자만 가지고 있지 않고, 이 원소를 시작점으로 삼은 구간이 실제로 가질 수 있는 시작점의 개수 라는 값을 저장합시다. 예를 들어서, 7개의 1이 있는 상황 $[1, 1, 1, 1, 1, 1, 1]$ 을 생각해 봅시다. 초기 각각에 연계된 시작점의 개수는 모두 1입니다. 고로 $[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)]$ 과 같이 pair로 저장할 수 있습니다. 만약에 $L = 3$ 에서 이를 level 2로 바꾼다면, 7개의 1은 2개의 2로 바뀝니다. 이 때 1개의 2를 시작점으로 삼는 경우는 $3 \ldots 5$ 번째 1을 시작점으로 삼는 것과 동일, 2개의 2를 시작점으로 삼는 경우는 $1 \ldots 2$ 번째 1을 시작점으로 삼는 것과 동일합니다. 고로 $[(2, 2), (2, 3)]$ 과 같이 압축할 수 있습니다. 일반화하면, 1개의 $x+1$ 을 시작점으로 삼는 경우는 $|A| - 2L + 2 \ldots |A| - L + 1$ 번째. 2개의 $x+1$ 은 $|A| - 3L + 2 \ldots |A| - 2L + 1$ 번째 라고 생각할 수 있습니다. 이러한 값을 저장하면, 손실되는 정보가 없이 매칭되는 정보를 찾을 수 있고, 이렇게 해서 전체 스택을 순회하면 매칭되는 시작점의 개수도 셀 수 있어, $O(n^2)$ 풀이를 유도할 수 있습니다.

위 방법에서 정보를 관리할 때 시작점 개수를 부분합으로 관리해 주면, $O(n\log n)$ 으로 복잡도가 줄어듭니다.

ONTAK 2009. Godzilla

먼저 다음과 같이 문제를 단순화합시다.

• $Q = M$이라고 가정합시다. $Q < M$일 경우 지워지지 않은 나머지 간선들을 지우는 쿼리를 추가한 후 출력할 때 무시하시면 됩니다.
• 간선을 제거하는 것이 아니라, 빈 그래프에 간선을 순서대로 추가한다고 생각합시다. 쿼리를 역순으로 처리하시면 됩니다.

하나의 쿼리에 대한 답은 문제에서 주어진 그래프에 대한 강연결 컴포넌트 (Strongly connected component) 를 만들면 알 수 있습니다. 그래프를 강연결 컴포넌트로 분리하면, 한 컴포넌트에서 하나의 정점만 선택하면 컴포넌트 상에 있는 모든 정점들을 덮을 수 있으며 이에서 도달할 수 있는 모든 정점들 역시 알 수 있습니다. 고로, indegree가 0인 컴포넌트에서 정점을 하나씩 선택하면, 나머지 컴포넌트들은 indegree로 들어오는 어떠한 방송 신호를 잡으면 됩니다. 고로, 문제의 정답은 indegree가 0인 SCC의 개수이고, 이는 $O(M)$에 계산할 수 있으니, 각 쿼리 당 SCC를 계산하는 식으로 문제를 $O(M^2)$ 에 해결할 수 있습니다.

이는 비효율적이니 빠른 풀이를 생각해 봅시다. 우리는 어떠한 간선에 대해서 이 간선이 잇는 두 정점이 같은 SCC에 속하는 시간을 계산하고자 할 것입니다. 만약 추가된 간선의 양 끝점이 같은 SCC에 속한다면 이 시점은 간선이 추가된 시점과 동일할 것이고, 그 외에는 다른 간선들이 적절히 추가되어서 간선의 반대로 가는 경로가 생기는 시점이 이 시점일 것입니다.

만약 이 시점을 모든 간선에 대해서 알 수 있다면, SCC를 관리하는 것을 Union-Find를 통하여 할 수 있습니다. 모든 간선에 대해서 해당 시간이 계산되었다면, 이 시간에 간선의 양 끝점을 Union-Find에서 합쳐줍시다. 이렇게 될 경우 컴포넌트는 관리할 수 있습니다. indegree 관리는 약간 까다로운데, 결국 우리는 어떠한 간선이 방향 간선으로 남는 시간의 구간을 알 수 있습니다. 이 시간 동안 해당 간선의 끝점에 indegree를 추가하고, 두 정점을 합쳐줄 때 이 indegree 값을 더해주며, 해당 간선의 수명이 다 했을 때 indegree를 제거하는 식으로 indegree를 관리할 수 있습니다. 이렇게 되면 indegree가 0인 정점의 개수 역시 관리해 줄 수 있으니, 문제를 해결할 수 있습니다.

해당 시점을 알아내는 것은 분할 정복을 통해서 할 수 있습니다. 흔히 말하는 parallel binary search와 비슷한 트릭으로, 각각의 간선에 대해서 시간 $m$ 에 양 끝점에 대해서 같은 컴포넌트에 속하는 지를 판별하고, 판별 결과에 따라서 시간 범위를 좁혀나가는 방식입니다.

• solve(L, R, E): $E$에 있는 간선이 $[L, R]$ 구간 안에 있는 시점에 같은 컴포넌트에 속하게 될 때, 이들이 정확히 같은 컴포넌트에 속하는 시점 계산

이라고 합시다. $M = \frac{L+R}{2}$ 에 대해, 시간 범위 [1, M]에 있는 모든 간선들을 모은 후 SCC를 만들어 줍시다. 이 제 이 중 [L, M] 구간 안에 있는 시점에 같은 컴포넌트에 속하게 되는 간선은, 인덱스가 M 이하이며, 만들어진 SCC에서 같은 컴포넌트에 속하는 간선들 뿐일 것입니다. 고로 각 간선이 [L, M]에 합쳐지는지, [M+1, R]에 합쳐지는 지 알 수 있습니다.

이 방법은 올바른 답을 찾지만, 모든 [1, M] 구간에 있는 간선을 보기 때문에 느립니다. 시간 범위 [1, M]에 있는 모든 간선들을 모으지 말고, 시간 범위 [1, M] 에 있는 E 상의 간선들만 보면 안될까요? 이것이 가능하기 위해서는 E 상에 없는 다른 간선들이 SCC를 어떻게 바꿨는지 알고 있어야 합니다. 결국 분할 정복 과정에서도 이러한 다른 간선들이 의미가 있는 것은 이 간선이 같은 SCC로 합쳐질 때이니, [1, L-1] 시점에서 같은 SCC로 어떻게 합쳐졌는 지의 정보를 가지고 있으면 모든 간선을 볼 필요 없이 분할 정복을 계속할 수 있습니다. 이는 분할 정복 정의를 다음과 같이 바꿈으로 해결할 수 있습니다:

• solve(L, R, E): $E$에 있는 간선이 $[L, R]$ 구간 안에 있는 시점에 같은 컴포넌트에 속하게 될 때, 이들이 정확히 같은 컴포넌트에 속하는 시점을 계산하고, 계산이 끝난 후 $[L, R]$ 구간에 있는 SCC를 모두 합침

합치는 과정은, 분할 정복의 단말에 도달했을 때 Union-Find에서 두 정점을 합쳐주는 연산을 하시면 됩니다. 까다로운 분할 정복이라 이해하기 쉽지 않은데, 이 문단을 포함하여 마지막 세 문단을 무시하고 직접 생각해 보는 것도 도움이 될 것입니다. 시간 복잡도는 $O(M\log M)$ 입니다.