2019.12.03 problem solving

NEERC Northern Subregional 2015 A. Alex Origami Squares

일반성을 잃지 않고 $w \le h$ 라고 합시다. 두 가지 케이스가 있습니다:

1. 세로로 길게 3개의 색종이를 늘어놓는 것.
2. ㄴ자 모양으로 색종이 3개를 늘어놓는 것.

각 케이스에 대한 색종이의 길이는 단순 비교 연산과 나눗셈으로 계산 가능합니다.

NEERC Northern Subregional 2015 J. Journey to the “The World’s Start”

먼저 몇 가지 사실을 짚고 넘어갑시다.

• 문제에는 출발지 방향으로 역행해도 된다고 되어 있으니, 굳이 역행을 해서 도움이 되는 경우는 없고, 목적지 방향으로 계속 움직이면 됩니다.
• 목적지 방향으로 계속 움직일 것이니, 이동에는 무조건 정확히 $N-1$ 시간이 소요됩니다. 고로 이동 시간을 고려할 필요가 없이 중간 경유지의 대기 시간 합만 최소화하면 됩니다.

교통 카드는 어차피 한 장만 구매하니까, 결국 교통 카드를 사는 것은 오가는 구간에 대한 길이 제한을 정하는 것이라고 생각할 수 있습니다. 길이 제한이 여유로워진다고 소요시간이 길어지지 않습니다. 고로 $T$분 안에 목적지에 도달할 수 있는 최소 길이 제한을 이분 탐색합시다. 최소 길이 제한을 알면 답은 쉽게 구할 수 있습니다.

범위 제한 $M$으로 목적지에 도달하는 최단 시간을 계산하는 문제를 생각해 봅시다. 위 관찰을 사용해서 다음과 같은 동적 계획법을 사용할 수 있습니다.

$DP[i] = max_{i+1 \le j \le i + M} DP[j] + T[i]$

이를 단순하게 구하면 $O(N^2)$ 이니 최적화해야 합니다. 가장 간단한 방법은 Heap을 사용하는 법입니다. 각 계산이 끝난 후 $(DP_i, i)$ 쌍을 Heap에 삽입합시다. $(DP_j, j)$ 에 대해, $j \ge i + M$이면 이 $j$는 만료되었다고 생각하고 제거할 수 있습니다. 이러한 만료된 원소들을 모두 제거하면, Heap에 있는 최솟값이 $i+1\le j\le i+M$ 조건을 만족합니다. 이 값을 토대로 DP를 계산하면 각 이분 탐색이 $O(N\log N)$ 에 빠르게 해결됩니다.

Deque를 사용해서 더 빠르게 해결할 수 있고, 이 방법도 지금 방법에 비해 크게 어렵지 않으니, 관심있는 분은 생각해 보시기 바랍니다.

CERC 2012. Jewel Heist

모든 색깔을 포함하지 않도록 보석을 가져간다는 것은, 하나의 색을 골라서 해당 색을 제외하고 최대한 많은 보석을 가져가게끔 노력한다는 것과 동일합니다. 어떠한 색 $c$를 골라서 해당 색을 피하도록 보석을 가져가는 방법을 모두 시도한 후 이를 합하는 접근을 시도해 봅시다. 보석을 가져가게끔 하는 $Y$좌표를 고정했을 때, $Y$좌표가 해당 점 이하이며 색이 $c$의 점이 있는 $X$좌표는 피해야 할 것입니다. 이러한 제약 조건 하에서 최대한 긴 구간을 잡으면 이러한 구간은 최대 $N_c$ (색이 $c$인 점의 개수) 개 나옵니다. 이를 모든 좌표에 대해서 해 보면 대략 $O(N_c^2)$ 개 의 구간이 나와서 문제를 해결하기 비효율적임을 알 수 있습니다.

관찰은 다음과 같습니다. 어떠한 후보를 시도할 때, 만약 이 후보의 바로 위쪽에 점 $c$가 없다면 (즉 $y = Y+1, X_l \le x \le X_r$ 구간에 점이 없다면) 이 구간을 고르지 않을 이유가 없습니다. 이런 식으로 계속 반복하면 무한히 높은 곳까지 다다르거나, 아니면 점 $c$ 를 바로 위에 두고 멈춥니다. 이 두 경우를 생각합시다:

• 무한히 높은 곳까지 다다랐다면, $Y = \infty$ 일 때 점이 있는 $X$좌표를 피하는 최대 구간들을 시도해 보면 됩니다. 이러한 구간은 $O(N_c)$ 개 있고 $X$좌표 순으로 정렬하면 구할 수 있습니다.
• 막힌 점이 있다면, 해당 점의 바로 아래를 중심으로, 왼쪽/오른쪽으로 뻗어나갔을 때 어느 위치에서 막히는 지를 확인하면 됩니다. 점에 따라 구간이 결정되니 이러한 구간은 $O(N_c)$ 개 있습니다. 이러한 구간은 $X$좌표가 정렬되어 있다면 Stack을 사용하여 $O(N_c)$ 에 계산할 수 있습니다. (X좌표가 같은 점을 조심해야 합니다)

이를 모든 점에 대해 반복하면 총 $O(N)$ 개의 로봇 팔 배치 후보를 $O(N\log N)$ 에 찾을 수 있습니다.

이제 실제로 해당 후보를 사용했을 때 몇 개의 보석을 먹을 수 있는지를 계산해야 하는데, 이는 후보들을 $Y$좌표로 정렬한 후 line sweeping을 하면 계산할 수 있습니다. 어떠한 $X$좌표 구간에 점이 몇 개 있는지를 효율적으로 계산하는 Fenwick tree 자료 구조를 동반하면 이 부분도 $O(N\log N)$ 시간에 가능합니다.

ICPC World Finals 2019 H. Hobson's Trains

문제에서 요구하는 것 그대로 각 정점을 도달할 수 있는 다른 정점을 세는 것이 아니라, 이를 뒤집어 각 정점에서 도달 가능한 서로 다른 정점을 마킹하는 식의 방법을 사용합시다. 이렇게 되면 문제는 두 개의 부분으로 분리됩니다.

• 도달 가능한 서로 다른 정점 수 세기
• 정점 수를 알 때 각 정점에 효율적으로 마킹하기

첫 번째 부분은, 주어진 입력이 사이클 여러개에 트리가 달려 있는 형태의 방향 그래프 (functional graph) 이니, 각 사이클에서 시작해서 트리 정점에 답을 확장시키는 식으로 문제를 해결합니다. 위상 정렬의 요령으로 indegree가 없는 정점을 반복적으로 제거하면 그래프에 사이클만이 남습니다. 각 사이클에서 도달 가능한 정점은 사이클의 정점 개수와 동일합니다. 각 트리에서 도달 가능한 정점은, 사이클 안에 있는 루트를 중심으로 거꾸로 DFS를 해 주면서 세어 줄 수 있습니다. 개수를 안다면, 각 정점에서 칠해야 할 정점의 개수는 $min(k+1, $도달 가능 정점 수) 입니다.

두 번째 부분은 여러 방법이 있습니다. 예를 들어 변홧값 배열과 비슷하게 $O(N)$ 시간에 처리할 수도 있습니다. 여기서는 $O(N \log N)$ 시간에 처리하는 방법을 소개합니다. 먼저 각 정점에 대해서, $par(k, x) = (x$에서 $2^k$ 번 움직인 후 도달 위치)를 모든 $2^k < n$ 에 대해서 구합시다. 이제 다음과 같은 배열을 정의합니다.

• $color(k, x) = x$를 포함해서, $x$에서 도달 가능한 첫 $2^k$ 개의 정점에 값을 더하고 싶음

각 정점에 대해서, $color(k, x)$ 에 1을 더해준 후 $par(k, x)$ 위치로 이동하는 걸 반복하면서 $O(\log N)$ 시간에 원하는 목표를 기록할 수 있습니다. $color(k, x)$에 $v$가 더해진 것은, $color(k-1, x), color(k-1, par(k-1,x))$ 에 $v$가 더해진 것과 동치이니, $k = \log N \rightarrow 1$ 으로 내려가면서, 최종적으로 $color(0, *)$ 에만 값이 저장되게 할 수 있습니다. 이제 이 배열을 출력해 주면 됩니다.

GCJ 2015 Round 2 C. 영어와 프랑스어

단어와 문장들의 집합들을 영어 / 프랑스어 라는 두 개의 분류로 분할해야 하고, 분할 과정에서의 비용을 최소화해야 합니다. 이러한 식으로 집합을 이분할해서 해를 최소화하는 유형의 문제는 Minimum Cut으로 풀리는 경우가 많습니다. 이 문제 역시 Minimum Cut을 통해 해결할 수 있습니다.

먼저 각각의 단어를 하나의 정수로 치환해서 생각합시다 (흔히 사용하는 “좌표 압축” 기법을 그대로 적용하면 됩니다.) 그래프를 만들 때는, 각각의 문장과 단어에 대해서 정점을 만들어 주고, 이 정점이 찾은 Cut에서 source와 연결된 쪽에 속하면 영어 단어/문장, sink와 연결된 쪽에 속하면 프랑스어 단어/문장 이라고 합니다.

Cut의 비용은 정답과 일치해야 하므로, 이 과정에서 간선을 끊는 데 든 비용이 영어이면서 동시에 프랑스어인 단어의 개수와 동일해야 합니다. 즉, 어떤 단어가 영어이면서 동시에 프랑스어일 때 1의 비용을 지불하게 해야 합니다. 이러한 제약 조건을 보았을 때 Minimum Cut을 가정한 우리의 풀이 전략은 매우 희망적입니다. 어떠한 단어가 영어이면서 프랑스어라는 것을 Minimum Cut의 관점에서 본다면, 이 단어는 source와 sink에 모두 연결되어 있습니다. 고로 어떠한 에지를 정확히 1개 끊어서, 이 단어가 둘을 연결하는 효과를 내지 못하게 해야 합니다. 이는, 단어에 대해서 두 개의 정점을 만들어 주고, 정점 두개가 모두 source 방향이면 영어, 정점 두개가 모두 sink 방향이면 프랑스어, 정점 하나가 source고 또 하나가 sink에 있으면 둘 다라고 판단해 주면 됩니다.

정점을 만들었으니, 이제 “영어 문장에 순수 프랑스어가 있으면 안된다” 류의 제약 조건을 만들어 줍시다. 문장 정점이 source 쪽 컷에 있으면, 포함하는 단어 정점 중 최소 한 쪽은 source 쪽 컷에 있어야 합니다. 고로 문장 정점에서 단어 정점(의 source와 가까운) 쪽으로 무한한 가중치의 간선을 이어줘서, 그렇지 않은 상황이 발생 치 못하게 해 줍니다. 반대로, 단어 정점(의 sink와 가까운) 쪽에서도 문장 정점으로 무한한 가중치를 이어서 문장 정점이 sink에 있는데 단어가 둘 다 source에 못 가도록 제약 조건을 만들어 줍니다.

마지막으로, 무조건 영어이고 프랑스인 문장들은 source / sink간에 무한한 가중치의 간선을 이어줘서 해당 조건을 만족시킵시다. 시간 복잡도는 입력의 제곱 정도에 비례하며, 실제로는 그보다 훨씬 빠르게 동작합니다.

GCJ 2013 Qualification D. Treasure

사전 순 최소로 방법을 찾아야 한다는 조건이 있는데, 일단 무시하고 방법이 있는지 없는지를 YES/NO로 판별하는 방법을 생각해 봅시다. 같은 종류의 키는 여러 상자를 열 수 있지만, 한 종류의 키가 단 하나의 상자만을 열 수 있다고 생각해 봅시다. 이 경우 문제는 그래프 탐색을 통해서 판별할 수 있습니다. 키를 가졌다는 것은 어떠한 상자를 열 수 있다는 것에 일대일 대응되기 때문에, 어떠한 상자를 열었을 경우, 다른 방문할 수 있는 상자들의 후보가 새로 추가된다고 생각할 수 있습니다. 이러한 과정을 통해서 모든 상자를 추가시키면 (즉 모든 상자에 도달 가능하면) 답은 YES고 아니면 답은 NO 입니다.

실제로는, 한 종류의 키는 실제로 여러 종류의 상자를 열 수 있습니다. 이를 위해서 각각의 종류의 키를 재분류 한다고 생각해 봅시다. 원래 한 종류의 키는 여러 상자를 열 수 있으나, 재분류를 하여서 한 종류의 키가 열 수 있는 상자가 단 하나가 되게끔 하는 것입니다. 재분류가 확실히 실패하는 상황은, 상자 전체에 존재하는 해당 종류의 키의 개수가 해당 종류의 키로 열 수 있는 상자의 수보다 적을 때 입니다. 이 경우에는 재분류를 할 경우 열지 못하게 되는 상자가 하나 남게 되어서 답이 No가 됩니다. 그렇지 않은 경우에도 재분류를 할 때 주의해야 합니다. 재분류의 결과로 인하여 탐색 이후 방문하지 못하는 상자가 생길 수 있기 때문입니다.

재분류를 어떻게 해야 모든 상자를 열 수 있을까요? 그래프 탐색을 할 때 상자에 대한 정점 외에도 키에 대한 정점을 만든 후 깊이 우선 탐색을 합시다. 어떠한 상자는 가지고 있는 키로 간선이 이어져 있고, 어떠한 키는 열 수 있는 상자로 간선이 이어져 있습니다. 키 정점에 대해서 들어오는 간선의 개수가 나가는 간선의 개수보다 작으면 답은 NO입니다. 이 그래프에서 모든 정점이 방문 가능하면 답은 YES입니다. 오일러 투어를 구하는 알고리즘을 응용하여 올바른 재분류 방법을 찾을 수 있기 때문입니다. 그래프를 만들고 탐색하는 것은 입력의 선형 시간에 간단하게 구현할 수 있습니다.

이제 답이 YES/NO인지를 판별하는 루틴을 완성했으니 이를 통해 사전 순 최소를 판별해 봅시다. 맨 처음 $B$ 라는 상자를 방문하는 수열이 존재한다는 것은,

• 맨 처음 가진 키 중 $B$를 여는 키가 존재하며

• 맨 처음 가진 키에서 $B$를 여는 키를 제거하고, $B$ 에 포함된 키를 모두 추가한 후, 상자 $B$ 가 없다고 쳤을 때 답이 YES

  인 것과 동치입니다. 사전 순 최소는 맨 처음 원소를 최소화하고, 그 후 다음 원소를 최소화하고, 이를 반복하는 그리디 알고리즘으로 구할 수 있습니다. 맨 처음 원소를 $B$ 라고 고정했을 때 수열을 완성할 수 있는 지를 위에서 만든 루틴으로 선형 시간에 판별할 수 있으니, 이를 $1 \cdots N$ 에 대해서 다 해보는 것을 $N$번 반복하면 사전 순 최소도 알 수 있습니다. 최악의 경우 루틴을 $O(N^2)$ 번 호출하니, 전체 문제가 $O(N^3)$ 정도에 판별됩니다.

Algorithmic Engagement 2011. Kangaroo

일반성을 잃지 않고 캥거루의 모든 시작/끝점이 $[1, 2N]$ 사이의 서로 다른 정수라고 가정합시다. 이는 실제 구현 단에서 좌표압축을 할 때, 시작점과 끝점의 홀짝을 다르게 주고, 위치만이 아니라 해당 위치의 구간 번호까지 관리하는 식으로 설정해 주실 수 있습니다. 각각의 쿼리의 시작/끝점이 다를 필요는 없으나, 이렇게 설정된 시작/끝점에 대응되게 역시 적절히 좌표 압축을 시행해 줍시다.

만약 쿼리로 묻는 구간이 모두 길이 1을 가진다면, 이 문제는 Segment Tree를 사용하여 해결할 수 있습니다. Segment Tree를 사용하면, 길이 N의 불리언 배열에 대해서 1로만 이루어진 최대 연속 구간의 길이를 반환할 수 있고, 업데이트 역시 지원하게 할 수 있습니다. 각각의 캥거루가 $A_i$지점을 지날때 삽입되고, $B_i$ 지점을 지날 때 삭제되면, 이러한 개의 지점에 대해서 세그먼트 트리에 업데이트를 진행하고, 업데이트 후 각 길이 1의 구간에 대한 쿼리 결과를 저장하면 됩니다.

쿼리의 구간이 마음대로일 수 있다는 것이 이 방법의 단점입니다. 하지만, Mo’s algorithm이라고 알려져 있는 평방 분할 기법을 사용하면, 각각의 쿼리를 처리할 때 쿼리의 끝점의 변경사항이 많아야 $O(N\sqrt M)$ 이 되게끔 할 수 있음이 잘 알려져 있습니다. 고로, 위와 같이 쿼리 정렬을 하면 다음과 같은 식으로 문제를 해결할 수 있습니다:

• 1번 쿼리에 대한 답을 brute force로 계산
• $i$ 번 쿼리에 대한 답을 알았을 때, 시작점과 끝점을 이동시키면서, 이동에 따라서 변하는 캥거루의 정보를 Segment Tree에 업데이트
• 이후 위 Segment Tree를 통해서 쿼리 계산

시작점과 끝점이 이동하면서 변하는 캥거루의 개수는 많아야 1개이니, Segment Tree에 $O(N\sqrt M)$번 연산을 하게 되어 총 시간 복잡도는 $O(N\sqrt M \log M)$ 이 됩니다.

GCJ 2008 World Finals E. The Year of Code Jam

일반성을 잃지 않고 격자의 외곽에 흰색 셀을 넣어서 격자를 $(N+2) \times (M+2)$ 크기로 키웁시다. 이렇게 하면 검은색 셀이 격자의 외곽에 닿는 일이 없게 되니, 다음과 같은 명제가 성립합니다.

명제. 행복도의 합은, 양 옆에 검은색 셀과 흰색 셀이 닿아 있는 변의 개수와 동일하다.

행복도의 합을 최소화한다고 하면, 이러한 문제를 Minimum Cut를 사용하여 모델링하면 해결할 수 있습니다. Minimum Cut은 그래프에서 두 정점의 연결을 최소한의 비용을 들여서 끊는 방법을 찾는 문제인데, 이 때 검은 셀과 흰색 셀을 대표하는 두 정점을 추가로 만들고, 검은 셀 정점 쪽에 연결되어 있는 셀은 검은색, 흰 셀 정점 족에 연결되어 있는 셀은 흰색이라고 간주합니다. 이 경우:

• 검은색 셀은 검은 정점과 무한한 가중치로 연결되어 있습니다. (고로 떼어질 수 없습니다.)
• 흰색 셀은 흰 정점과 무한한 가중치로 연결되어 있습니다. (고로 떼어질 수 없습니다.)
• 격자 상에서 인접한 두 정점은 1의 가중치로 연결되어 있습니다. (고로 다른 색이 배정될 경우 1의 비용이 추가됩니다.)

Minimum Cut은 다항 시간에 해결할 수 있음이 잘 알려져 있으나, 이 문제에서는 행복도의 합을 최대화하는 Maximum Cut 문제를 해결해야 합니다. Maximum Cut은 NP-hard이니, 약간의 발상의 전환이 필요합니다.

만약 격자 상에서 색이 칠해진 격자가 없고 모든 셀이 물음표로 쳐져 있다면, 체스판과 같이 인접한 두 셀에 항상 다른 색이 가도록 칠하는 것이 항상 이득입니다. 이러한 점에서 착안하여 문제를 해결합시다. 격자 상에 있는 모든 점을 반전하여서, $i+j$ 가 짝수인 점은 흰색을 검은색, 검은색을 흰 색으로 간주합시다. 이제 명제를 다음과 같이 변형할 수 있습니다.

• 명제. 행복도의 합은, 양 옆에 같은 색의 셀이 닿아 있는 변의 개수와 동일하다.

같은 색의 셀이 닿아 있는 변의 개수를 최대화하는 것은, 다른 색의 셀이 닿아 있는 변의 개수를 최소화하는 것과 똑같은 문제입니다. 고로, 위에서 설계한 Minimum Cut 루틴을 그대로 사용한 후, 모든 인접한 두 셀 쌍의 수에서 이 값을 빼면 답을 찾을 수 있습니다.

ICPC World Finals 2019 I. Karel the Robot

이 문제는 언어 파싱을 통해서 해결을 시도해 볼 수 있습니다. 문법이 간단하고 해석에 크게 모호함이 없어서 파싱은 간단한 편입니다. 이렇게 문제에 나와 있는 형식 그대로 구현을 시도하면 몇 가지 문제점을 제외하고는 대부분 올바르게 구현할 수 있습니다.

위 구현의 문제점은 무한 루프를 판별하지 못한다는 것과, 시간 복잡도가 매우 크다는 것입니다. 다음과 같이 해결하실 수 있습니다.

시간 복잡도 문제는 같은 프로시저를 지수적으로 호출하게 되면서 생기는 일입니다. 현재 로봇의 상태에 따라서 프로시저의 결과는 결정됩니다. 고로 dp(procedure, state) = 어떠한 프로시저를 state 상태로 실행했을 때의 결과. 와 같이 메모이제이션 해주시면 각 state를 중복하여 계산하지 않기 때문에 해결됩니다.

무한 루프는 프로시저 호출이나 while 문의 실행에서 생길 수 있습니다.

프로시저 호출 과정에서 무한 루프가 돈다는 것은, call stack에 같은 프로시저를 같은 상태로 실행했다는 것입니다. 고로 dp 상태와 비슷하게, 현재 콜 스택에 어떠한 상태가 있는지를 배열에 저장해 주시면, 프로시저 호출 과정에서 생기는 무한 루프는 찾아주실 수 있습니다.

while 문 실행 과정에서 무한 루프가 돈다는 것은, while 문을 실행하면서 원하는 상태에 절대 도달하지 못하고 계속 맴돈다는 것입니다. while 문 안의 프로그램은 상태를 바꾸는 역할을 하는데, 이 프로그램이 상태를 원하는 상태로 못 바꾸고 사이클에 빠지면 무한 루프가 생기게 됩니다. 고로 while 문을 돌면서 지금까지 방문된 상태를 배열에 기록해 두시면, 무한 루프가 생기는 지 아닌지를 역시 확인할 수 있습니다.

입력이 작아 정확한 시간 복잡도 계산은 필요 없으나, 해 보시면 대략 입력 크기의 세제곱에 비례합니다.

(주인장 징징: 4팀 풀린 문제 + 약한 분야인 파싱이라서 긴장하고 읽어봤더니 그냥 존나 쉬운 문제였다. 에휴..)

BOI 2018. Alternating Current

어떠한 철로 $X$가 덮는 구간이 철로 $Y$가 덮는 구간에 완전히 포함된다고 가정해 봅시다. 이 경우, 철로 $X$의 방향은 $Y$와 다르다고 가정할 수 있습니다. 만약 다르지 않다면, 반대 방향으로 $X$를 뒤집었을 때, 시계/반시계 방향에서 덮이지 않은 철로는 생기지 않으며 오히려 반대 방향으로 철로를 덮을 수 있기 때문입니다. 이 관찰은 두 가지 결론을 함의합니다.

• 어떠한 철로가 다른 철로를 포함하는 관계가 없는 철로들에 대해서만 방향 배정을 해 주면, 나머지는 자동적으로 방향을 배정할 수 있다.
• 어떠한 철로 $X$가 철로 $Y$에 포함된다면 $X$가 덮는 구간에는 철로가 양방향으로 설치되어 있다.

고로 어떠한 철로가 다른 철로를 포함하는 관계가 없다고 하고 문제를 해결해 봅시다. 2번 결론에 의해서 이미 철로가 양방향으로 설치된 것이 확정된 구간들은 덮을 필요가 없으니, 양방향으로 덮인 구간은 원래부터 존재하지 않았다고 가정하고 제거합시다. 이제 일반성을 잃지 않고 원래 문제와 동일하지만 어떠한 철로가 다른 철로를 포함하는 관계가 없을 뿐인 인스턴스를 생각할 수 있습니다. 이에 대해서 다음과 같은 Lemma가 성립합니다.

• Lemma 1. $M$ 이 짝수일 때, $M$개의 철로를 시작점 순으로 정렬했을 때의 최적 배정은, 010101010101 과 같이 모든 인접한 철로에 다른 방향이 배정되는 형태이다.

• 증명. 만약 위 알고리즘이 배정에 실패한다면, 배정에 실패한 구간을 덮는 철로는 많아야 하나라서, 어떠한 방법으로도 덮을 수 없는 입력입니다. 고로 위 알고리즘은 모든 가능한 입력에 대해 답을 찾습니다.

이를 조금 응용해서 $M$ 이 홀수인 경우도 해결 가능합니다.

• Lemma 2. $M$ 이 홀수일 때, $M$ 개의 철로를 시작점 순으로 정렬했을 때의 최적 배정은, 0101101010101 과 같이 단 하나의 쌍을 제외하고 모든 인접한 철로에 다른 방향이 배정되는 형태이다.

• 증명. $M$이 홀수일 때는 무조건 같은 방향이 배정되는 인접한 철로 쌍이 존재할 수 밖에 없습니다. 이들을 하나의 구간이라고 가정하면 (만약 그 사이에 빈 공간이 있다면 어차피 답이 되지 못합니다) 이제 $M$이 짝수이니 Lemma 1의 알고리즘을 사용하면 됩니다.

관찰을 종합하면, 가능한 배정은 많아야 $O(M)$개라는 것을 알 수 있습니다. 포함 관계가 없는 구간들에 대해서 Lemma 1/2에서 제시된 $M$개의 배정을 전부 시도해 보면, 나머지 포함 관계가 있는 구간들의 방향은 자동적으로 정해지기 때문입니다. (이들을 포함하는 임의의 다른 포함 관계 없는 구간을 잡은 후, 그 구간의 정반대 색을 칠해주면 됩니다.) 자신을 포함하는 다른 구간이 존재하는 지를 찾는 것은 일단 naïve하게 각 구간마다 $O(M)$ 시간에 할 수 있으니 (원형으로 넘어가는 것과, 완전히 동일한 구간에 대한 처리, 전체를 덮는 구간에 대한 처리를 주의합시다) 일단 이 부분을 $O(M^2)$ 에 처리합시다.

어떠한 배정이 모든 구간을 덮는지는 $O(M)$ 시간에 판별할 수 있으나, 여기서는 이후 최적화를 위해서 Segment Tree를 사용합니다. 다음과 같은 연산을 지원하는 Segment Tree를 각 방향에 대해서 만듭니다:

• 구간에 특정한 숫자 더하기
• 전체 최솟값 구하기

이제, 각 배정에 대해서, 해당 구간에 배정된 방향을 나타내는 Segment Tree에 +1을 더하고, 전체 최솟값이 0인지 아닌지를 판별하는 식으로 (0이면 덮이지 않은 구간이 있으니 올바르지 않습니다) 문제를 해결할 수 있습니다. 고로 각 배정에 대해서 $O(M \log M)$ 시간이 걸리게 됩니다. 이로서 전체 문제는 $O(M^2 \log M$) 에 해결됩니다.

이제 두 부분을 최적화합시다.

포함 구간 구하기. 각 구간을 길이 역순으로 정렬한 후, 구간 최댓값을 구하는 Segment Tree를 사용합니다. 원을 두 바퀴 돌아 $2n$ 길이의 직선으로 생각할 것인데, 원을 넘어가는 구간은 $[a_i, b_i + n]$ 꼴로 저장하고, 그렇지 않은 구간은 $[a_i, b_i], [a_i + n, b_i + n]$ 과 같은 두 개의 꼴로 저장합니다. 직선 상에서 구간을 포함하는 다른 구간이 존재하기 위한 조건은, 시작점이 자신 이하이며 끝점이 자신 이상인 구간의 존재 여부입니다. 고로 각 시작점에 대해서 가장 큰 끝점을 Segment tree에 저장하면 구간 최댓값 쿼리로 환원되어 $O(M\log M)$ 에 문제가 해결됩니다.

배정 판별 최적화. 다음과 같은 방향 배정을 모두 해 보면 됩니다:

001010101010101

011010101010101

010010101010101

010110101010101

..

포함 관계가 없을 경우, 위에서 아래로 가면서 뒤집히는 구간은 단 하나입니다. 포함 관계가 있을 경우, 위에서 아래로 가면서 뒤집히는 구간은 해당하는 구간과, 그 구간에 포함된다고 계산했던 다른 구간들입니다. 어떠한 경우에서도 각 구간은 방향이 많아야 1번 뒤집힙니다. 구간을 제거하는 것은 Segment Tree에 -1을 더하는 것으로 처리할 수 있으니 결국 구간의 방향을 뒤집는 것은 2번의 Segment Tree 연산으로 가능합니다. 고로 전체 문제가 $O(M\log M)$ 에 해결됩니다.

ICPC Tsukuba 2017. Homework

동전 던지기가 없이 하나의 과제 종류만 있다면, 제출 기한이 가장 짧은 순으로 과제를 하는 것이 언제나 최적의 전략입니다. 고로 문제에 적혀있는 알고리즘은 최적 알고리즘이고, 철수가 매일 할 과목을 정했다면, 철수는 그 이후 최적의 알고리즘을 사용해서 그 과제들을 완수합니다. 이제 최댓값과 최솟값을 구하는 방법을 따로 생각해 봅시다.

최댓값: 위와 같은 관찰이 있다면 매우 쉽습니다. 어떠한 과목에서 왔는 지를 무시하고 최적 알고리즘을 사용하여 계산하면 되기 때문입니다. 문제에 적혀 있는 그대로 구현하면 됩니다. (특별히 인덱스 순서를 고려할 필요는 없습니다.)

최솟값: 하나의 과제 종류가 있다면, 문제에 적혀 있는 그리디 알고리즘이 아니라 이분 매칭을 사용해서도 최대 과제 개수를 계산할 수 있습니다. 날짜와 과제를 정점으로 만들고, 각 과제를 할 수 있는 날 관계를 간선으로 이어준 후 최대 매칭을 구하면 정답을 찾을 수 있습니다.

이분 매칭은 특정 그래프의 최대 유량이고, 최대 유량은 최소 컷 (Min-cut max-flow theorem) 입니다. 고로 우리는 각 날짜에 풀게 될 과목을 적절히 배치해서 최소 컷의 합을 최소화하는 문제를 해결한다고 볼 수 있습니다.

다음과 같은 그래프를 생각해 봅시다. (모든 유량은 1입니다)

위쪽 그래프는 수학 과제에 대한 이분 그래프에 해당되고, 아래쪽 문제는 컴퓨터 과제에 대한 이분 그래프에 해당되며, 사진은 이 둘을 합친 형태입니다.

어떠한 간선 집합 $E$ 를 잘랐을 때, 아래쪽 그래프에서 도달 가능한 날짜들의 집합을 $S$라고 합시다. $S$에 없는 날짜 ($S^C$) 에는 컴퓨터, $S$에 있는 날짜에는 수학 과제를 한다고 하면, 위쪽 그래프에서 잘린 간선들은 $S$집합을 막는 Min-cut, 아래쪽 그래프에서 잘린 간선들은 $S^C$ 집합을 막는 Min-cut이 됩니다. 고로, 위 그래프에서 최소 컷을 구하면 그만큼의 답을 가지는 집합을 찾을 수 있습니다. 반대로, 모든 $S$에 대해서 위 아래 따로 최소 컷을 구하고, 이들을 합쳐도 위 그래프에서 컷이 되기 때문에, 모든 집합에 대한 최소 컷은 위 그래프의 최소 컷과 일대일 대응 됩니다.

고로, Maximum Flow 알고리즘을 사용하시면 $O(n^3)$ 정도에 문제를 해결하실 수 있습니다.

NEERC Northern Subregional 2015 K. Kingdom Trip

동적 계획법의 아이디어를 사용하면, $O(n^3)$ 풀이를 찾는 것은 그렇게 어렵지 않습니다. $DP[i] = (i$번 위치에 도착하는 데 방문한 정점의 수), $Path_{i, j} = (i, j$ 를 직접 이동할 수 있는가) 라고 정의합시다. 점화식은 다음과 같습니다.

$DP[i] = min_{0 \le j \le i-1 \land Path_{i, j}} DP[j] + 1$

DP 표는 빠르게 채울 수 있으니 문제를 해결하기 위해서는 Path 표를 빠르게 채워야 합니다. 여기서, 문제를 해결하는 데 큰 도움을 주는 아주 중요한 사실 하나를 짚어 보겠습니다.

Lemma. 두 점 $p, q$ 를 잇는 선분은, $p$ 에서 $q$ 를 향하는 반직선과, $q$ 에서 $p$ 를 향하는 반직선의 교집합니다.

증명은 자명합니다. 이제 $Path_{i, j}$ 가 참이라는 것은:

• 모든 $i <k<j$ 에 대해, $i$에서 $j$방향으로 향하는 반직선과 점 $k$와의 거리가 $d$ 이하. (이를 $RPath(i, j)$ 라 함)
• 모든 $i <k<j$ 에 대해, $j$에서 $i$방향으로 향하는 반직선과 점 $k$와의 거리가 $d$ 이하. (이를 $LPath(i, j)$ 라 함)

이제 일반성을 잃지 않고 $RPath(i, j)$ 테이블을 빠르게 채우는 방법만 서술합니다.

고정된 $i$에 대해서 $j$를 증가시켜 나가면서 $RPath(i, j)$ 를 각각 $O(1)$에 채우는 식의 접근을 사용합니다. 어떠한 $k$에 대해서, 만약에 이 점이 $i$와의 거리가 d 이하라면, 이 점은 어떠한 반직선과도 거리가 d 이하이니 전혀 방해가 되지 않습니다. 그렇지 않다면, 이 점은 특정한 각도 범위에 있는 반직선만 받아 들일 수 있고, 다른 각도에 있는 반직선은 모두 이 점과의 거리가 d를 초과하게 됩니다. 이 각도 범위는, 점 k를 중심으로 한 거리 d의 원을 그렸을 때의, i의 두 접선이 이루는 각도 범위와 동일함을 알 수 있고, 고로 삼각함수를 통해 계산할 수 있습니다. 어떠한 j가, 그 사이에 있는 모든 k와 거리가 d 이하라는 것은, 이 각도 범위의 교집합 안에 j를 향한 반직선이 들어간다는 것입니다. 고로, 초기에 각도 범위를 전체 원으로 설정한 후, j를 늘려가면서

• $j$를 향하는 반직선이 이 각도 범위 안에 들어가는지를 계산하고 (이 결과로 $RPath(i, j)$ 를 채울 수 있음)

• $j$를 중심으로 한 원을 그려 새로운 각도 범위 제한을 알아내고, 교집합을 취함

  을 반복하면 됩니다. $LPath$ 배열도 똑같이 채우시면 됩니다. 시간 복잡도는 $O(n^2)$ 입니다.

NEERC 2018 I. Interval-Free Permutations

어떠한 부분 수열 (subsegment) $[L, R]$ 이 올바르다는 것은, $[p_L, \ldots, p_R]$ 이 구간 조건을 만족하며, 부분 수열의 길이가 $N-1$ 이하 (즉 전체가 아님) 이라는 것을 뜻합니다. 이러한 것 중, 어떠한 다른 올바른 부분 수열에 포함되지 않는 부분 수열을 올바른 극대 부분 수열 이라고 정의합니다. 이제 여러 개의 Lemma를 제시합니다.

• Lemma 1. 올바른 부분 수열 $X, Y$에 대해 $X \cap Y \neq \emptyset$ 이라면, $X\cup Y, X - Y, Y - X$ 역시 올바른 부분 수열이다.

• Proof. 약간의 케이스 분석으로 검증할 수 있으며 생략한다.

• Lemma 2. 임의의 위치 $1 \le i \le N$ 에 대해서 해당 위치를 포함하는 올바른 극대 부분 수열이 존재한다.

• Proof. $[i, i]$ 는 올바른 부분 수열이다. 이를 극대일 때까지 크기를 증가시키면 된다.

• Lemma 3. 만약 서로 다른 올바른 극대 부분 수열 $X, Y$에 대해 $X \cap Y \neq \emptyset$ 이라면, $X, Y$ 는 전체 구간이다.

• Proof. Lemma 1에 의해 $X \cup Y$ 는 올바른 부분 수열을 이룬다. 고로 합집합의 길이가 $N-1$ 이하일 경우 극대 조건에 모순이고, 이들의 합집합은 전체 구간이다.

이제 두 가지 케이스를 고려합니다.

• Case 1. $[1, i]$ 형태이며 $i\neq N$ 인 올바른 부분 수열이 존재. 위 조건을 만족하는 모든 $1 \le i \le N-1$ 를 고정점 이라고 부르자. 또한 모든 고정점에 대해서 $[i + 1, N]$ 역시 올바른 부분 수열이 된다.
• Case 2. 그러한 수열이 없음. 이 경우, 서로 다른 두 올바른 극대 부분 수열에 대해 $X \cap Y = \emptyset$ 가 항상 만족된다. Lemma 2와 종합하면, 극대 부분 수열들이 전체 배열을 분할하는 형태가 되며, 이 때 전체 극대 부분 수열의 개수는 3개 이상 $N$개 이하일 것이다.

이제 답을 계산합니다. 문제의 정답 $Ans_n$은 $n! – ($구간이 존재하는 순열의 개수) 라는 것을 알 수 있습니다. 구간이 존재하는 케이스는, Case 1과 같이 고정점이 있거나, Case 2와 같이 그렇지 않은 경우로 나뉘어집니다.

• Case 1과 같이 고정점이 있는 경우, 첫번째 고정점의 위치를 $i$ 라고 합시다. $[1, i]$ 부분배열의 원소가 $[1, i], [N-i+1, N]$구간인 두 가지 경우가 존재하는데, 두 경우 모두 고려합시다. $F_n = ($고정점 없는 순열의 수) 라고 정의하면, 이에 관한 식으로 답을 풀어 쓸 수 있습니다. $F_n$ 은 포함 배제 + DP로 계산해 주시면 됩니다.

• Case 2와 같이 고정점이 없는 경우, 극대 부분수열의 크기가 2 이상인 것이 하나라도 존재하면 답이 되지 않습니다. 고로 극대 부분수열의 개수가 3 이상 $N-1$ 개 이하인 경우에는 답으로 세면 안 된다는 뜻입니다. 극대 부분 수열이 $T$개 있다면, 이 각각의 부분 수열을 하나의 원소로 보았을 때, 이 원소들 역시 구간 없는 순열을 이뤄야 합니다. 고로, 각각의 “원소” 를 채우는 방법을 먼저 계산하고, 이들의 곱을 취한 후 여기에 $Ans_T$ 를 곱하면 됩니다. (다행이도 $T < N$ 이라 재귀적으로 올바릅니다.) 각각의 원소를 채우는 방법은, $DP[i][j] = \sum_{k= 0}^{j - 1} DP[i-1][k] (j-k)! $ 와 같은 간단한 점화식으로 해결하실 수 있습니다. 이 부분이 가장 느린 부분이라 시간 복잡도가 $O(n^3)$ 이 됩니다.

여담으로, 예외 케이스가 있는데, 어느 부분이 문제인지 직접 찾아 보시기 바랍니다 :)