2018.12.01 problem solving

난이도 순입니다.

1. ARC 051. Sum of Three Integer

$A, B$ 를 정하면, $C = S - A - B$ 로 자동으로 정해집니다. 고로 모든 $A, B$ 를 이중 루프로 순회하고, $0 \leq C \leq K$ 를 확인하면 됩니다. $A, B$의 가짓수가 각각 $K+1$개이니 시간 복잡도는 $O(K^2)$입니다.

포함배제 원리를 사용한 $O(1)$ 풀이도 있지만, 이 문제에서는 필요 없습니다.

2. POI 1997. Canoes

먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물론 몸무게가 무거운 사람을 보내는 것이 현명합니다. 두 번째, 세 번째로 가벼운 사람들에게 이를 반복하고, 같이 태워 보낼 수 있는 사람이 없을 때까지 이를 반복합니다.

이 알고리즘의 구현은, 정렬된 배열에서 현재 보낼 무거운 사람의 “포인터” 를 가지고 있으면 간편합니다. 가벼운 사람이 있을 때, 이 사람의 몸무게를 맞출 수 있을 때까지 포인터를 앞으로 (몸무게가 감소되는 쪽으로) 내려주고, 그 사람과 매칭시킨 후, 포인터를 다시 내려줍니다. 시간 복잡도는 $O(n\log n)$ 정도입니다. 입력 크기가 작아 정렬을 할 때 카운팅 정렬을 써도 됩니다.

이 그리디 알고리즘의 정당성은 다음 Lemma에 의해 보여집니다.

Lemma. 2인 보트를 T번 보낼 때, 가장 가벼운 T명이 서로 다른 2인 보트에 타는 해가 항상 존재한다.

증명은 귀류법으로 가능합니다. 문제의 난이도에 비해서 증명이 그렇게 쉽지 않습니다. 여기서는 생략합니다.

다른 방법으로는, 답 $T$에 대해서 이진탐색한 후, $a_i + a_{2T-1-i}$가 모든 $0\leq i < T$에 대해서 성립하는 지 보는 것입니다. 역시 시간 복잡도는 $O(n\log n)$이며, 정당성은 위 Lemma에 의해 자명합니다.

3. NAIPC 2018. Missing Gnomes

결과 수열의 숫자를 왼쪽부터 순서대로 채워 나갑시다. 선택지는 두 가지입니다.

1. 현재 부분 수열의 맨 앞에 있는 원소를 골라서 넣기. 이 수를 넣으면 부분 수열의 맨 앞 원소는 사라지고 뒤에 있는 원소가 하나씩 앞으로 밀릴 것입니다 (Queue와 비슷).
2. 부분 수열에 올라오지 않았던 원소 중 하나를 골라 넣기. 원소를 고를 때는 당연히 가장 작은 원소를 고르는 것이 좋습니다.

이 두 가지 경우 중 가장 작은 숫자가 나오는 경우를 그때 그때 Greedy하게 고르면 됩니다. 사전순 비교는 앞에서부터 차례대로 보면서 처음으로 숫자가 다를 때 비교를 멈추기 때문에, 여러 경우가 있다면 맨 앞에 있는 원소를 최소화하는 게 가장 중요합니다. 고로 이러한 Greedy 전략은 올바릅니다.

 

4. 2011 USP Tryouts. Card Show

이 문제는 제한이 (아주 작지는 않지만) 작은 편이기 때문에 다양한 풀이가 존재할 수 있습니다. 여기서는 가장 깔끔하고 또한 효율적인 $O(52n + q\log n)$ 풀이를 소개합니다. 더 느리지만 생각하기 쉬운 풀이가 있을 수도 있습니다.

일반적인 구간 갱신 / 구간 합 문제에서 가장 자주 사용되는 구조인 Segment Tree를 사용해 봅시다 (자료 구조에 대한 설명은 생략합니다). 카드 덱의 각 위치에 대해서 구간 합을 저장하는 Segment Tree를 만들어 줍니다. 위치는 52개이니 이러한 Segment Tree를 시간과 공간 제약 안에서 만들 수 있습니다. Segment Tree를 만든 후에는, 구간 합 쿼리를 51번 Segment Tree에 질의를 날리는 것으로 해결할 수 있습니다.

이제 구간에서 두 원소를 바꿔주는 쿼리를 생각해 봅시다. 이 쿼리에는 I번 트리와 J번 트리만이 관여되어 있으니, 이 두 트리에 대해서만 생각해 주면 됩니다. 우리가 원하는 것은 I번 트리의 특정한 구간이 J번 트리의 같은 구간과 교환되는 것입니다. 이 때, I번 트리와 J번 트리가 모양을 바꾸는 구간은 동일하다는 것을 생각해 봅시다. 만약 그것이 생성된 과정이 같다면, 해당 구간에 대응되는 $O(\log n)$ 개의 서브트리 역시 동일한 모양을 가질 것입니다. 고로, 우리는 단순히 이 서브트리들을 떼어서 서로 바꾸어 주면 됩니다.

교환해야 하는 서브트리는 일반적인 구간 쿼리의 요령으로 찾을 수 있습니다. 서브트리 하나를 교환하는 것이 어렵다고 생각할 수도 있으나, 어떠한 노드의 자식을 포인터의 형태로 가지고 있으면, 단순히 루트 노드를 교환하는 것만으로 서브트리 전체를 교환할 수 있으니 간단합니다.

 

5. NEERC 2016 M. Mole Tunnels

DP에 기반해서 문제를 풀기에는 문제의 제약 조건이 너무 크고, 효율적인 DP를 고안하기에 상황이 적절하지 않습니다. 한편, 문제의 설정 상 두더지가 한 마리씩 들어올 때마다 올바른 답을 출력해야 합니다. 이러한 설정은 기존보다 문제를 어렵게 하지만, 새로운 두더지가 들어왔을 때, 기존 답을 토대로 어렵지 않게 해결하는 방법이 있음을 시사하기도 합니다.

이러한 방식으로 문제를 접근해 봅시다. $i-1$ 마리의 두더지가 이미 자리를 잡은 상황에서 $i$ 번째 두더지가 들어 왔을 때의 배정을 생각해 봅시다. 가장 가까운 빈 위치에 두더지를 배정하는 것이 먼저 머릿속에 와닿지만, 당연하게도 제대로 되지 않습니다. 나중에 그 위치가 더 효율적인 다른 두더지가 올 수 있기 때문입니다. 올바른 배정 방법을 찾으려면 기존 두더지들이 만들었던 선택을 변형시킬 필요가 있으며, 현재 두더지의 선택도 차후 적용될 변형에 따라서 유동적이어야 합니다.

$i-1$ 마리 두더지 각각에 대해서, 각자의 생활 공간에서 밥을 먹는 위치를 잇는 경로에 화살표를 그어봅시다. 만약에 $i-1$ 마리의 두더지가 최적의 방법으로 식사하고 있다면, 트리 상 각 간선 $u - v$ 에 대해서 $u \rightarrow v$ 방향으로 움직이는 두더지와 $v \rightarrow u$ 방향으로 움직이는 두더지가 같이 존재하지 않습니다. 이 경우 그러한 두더지 두개의 목적지를 바꿔서 더 좋은 답을 찾을 수 있기 때문입니다.

새로운 두더지가 들어왔고, 목적지를 임의의 정점 $v$ 로 두었다고 합시다. 경로를 순서대로 따라갔을 때, 반대 방향으로 향하는 두더지를 중간에 만날 수 있습니다. 이러한 경우, 그 두더지와 목적지를 바꿔주고, 현재 두더지를 그 두더지로 바꿔주면 1만큼 거리를 오히려 줄이는 꼴이 됩니다. 고로, 만약에 경로 상에서 두더지를 반대 방향으로 만났다면 가중치가 -1, 그렇지 않다면 가중치가 1이 됩니다.

이렇게 그래프에 “변형된 가중치” 를 주면, 단순히 가장 거리가 짧은 정점을 찾은 후, 그 곳에 두더지를 배정하면, 현재의 선택이 기존의 선택을 최적화할 수 있으며, 미래의 선택에도 바뀔 수 있는 여지가 생깁니다. 이 알고리즘은 실제로 정당하며, 그 증명에 대해서는 후술합니다.

변형된 가중치는, 각각의 간선에 대해서 현재 이 간선을 윗방향 / 아랫방향으로 지나는 두더지가 몇 마리인지를 관리하면 찾을 수 있습니다. 이제, 트리에서 주어진 점과 가장 가까운 점을 찾는 방법은 단순 DFS로 $O(N)$ 에 가능하고, 간선을 갱신해 주는 것은 $O(\log N)$ 에 가능합니다. 간선 갱신이 $O(\log N)$ 인 이유는 이진 트리라서 경로의 길이가 항상 $O(\log N)$ 이하이기 때문입니다. 현재 시간 복잡도는 $O(NM)$ 입니다.

여기에 DP를 조합하면 시간 복잡도를 줄일 수 있습니다. 각각의 노드에 대해서, DP[i] = (i번 노드의 서브트리 중 i번 노드와 가장 가까운 정점, 그리고 그 거리) 를 저장합시다. 두더지가 새로 들어오는 정점을 $u$라고 하고, 가장 가까운 정점을 $v$ 라고 합시다. $LCA(v, w) = k$ 인 정점들은, 정점 $k$와, $k$의 자식 중 $v$ 와 반대편에 있는 정점의 서브트리들일 겁니다. 첫번째는 단순하게 계산해 주고, 두번째는 DP값을 단순히 참고하면 됩니다. 이를 $v$를 타고 올라가면서 계산해 주면 가장 가까운 정점을 $O(\log N)$ 에 계산할 수 있습니다. 계산이 완료 되면 경로가 추가되고, 가중치가 갱신됩니다. 고로, DP값을 갱신해야 합니다. 이 때는, 변동이 있는 노드들이 $v, w$의 조상들이기 때문에, 이들에 대해서만 새로운 값을 bottom-up으로 구해주면 됩니다. 이 역시 $O(\log N)$ 입니다. 고로, 두더지 하나를 새로 넣는데 $O(\log N)$ 시간이 걸려 시간 복잡도가 $O(M \log N)$이 됩니다. 생각의 과정이 길지만, 코드는 짧은 편입니다.

알고리즘의 정당성 증명은 Minimum Cost Flow라는 개념을 사용합니다. 이보다 더 간단한 방법이 있을 것이라고도 생각이 들지만, 개념을 알고 있다면 가장 쉽고 일반화하기 좋은 증명 방법이 됩니다. 이 문제를 Minimum Cost Flow의 instance로 모델링하면, 사실 위 알고리즘은 Minimum Cost Flow를 트리에서 돌리는 과정을 약간 추상화한 형태에 불과합니다.

대다수의 Greedy 알고리즘은 제한된 형태의 문제만 풀 수 있는 경우가 많지만, Minimum Cost Flow와 같은 Network Flow류 알고리즘은 Greedy 패러다임에 기반해 있으면서도 아주 다양한 조합 최적화 문제를 해결할 수 있는 강력한 해결법입니다. 풀이를 이해하는 데 어려움이 있거나, 비슷한 유형의 풀이에 관심이 있다면 Network Flow / Minimum Cost Flow에 대해서 알아보는 것을 추천합니다.

 

6. BOI 2013. Vim

먼저 문제의 최적해에 대한 성질을 고찰합시다. 문제에서 왼쪽으로 가는 연산은 모두 h 동작을 사용해야 하고, 오른쪽으로 가는 동작은 모두 f 동작을 사용해야 합니다. 물론 x 동작 역시 매우 중요하지만, 이 문제에서는 그냥 모든 e를 만나게 하고, 그 과정에서 보일 때마다 지워주면 되니 최적해와는 크게 상관이 없다 볼 수 있습니다. 이 때 사용할 수 있는 중요한 성질은 다음과 같습니다.

Lemma 1. 최적해에서는, h 동작을 사용해서 두 번 이상 지나치는 점이 없다.

이 때 "h 동작을 사용해서 지나쳤다" 라고 함은, h 동작을 썼던 점이거나, h 동작의 대상이 되었던 점이라는 뜻입니다. Lemma 1의 증명은 은 최단 경로가 단순 경로인 것과 비슷한 이유이고 어렵지 않습니다. 이 Lemma는 문제에서 가장 중요한 핵심 아이디어이고, 문제의 최종 풀이 역시 이와 같은 관찰에 비롯합니다.

하지만 여기서 바로 동적 계획법을 시도하는 것보다는 문제를 조금 더 단순화하는 것이 유리합니다. 위에서 힌트처럼 나왔던 사실은, x 동작이 실제로는 커서의 이동에 큰 영향을 주지 않는다는 것입니다. 여기서 조금 더 나아가, x 동작 자체의 존재 여부를 없애 버릴 수도 있습니다.

여기서 몇가지 아이디어를 생각해 봅시다. 우리는 문자열 상에서의 e의 존재를 명시적으로 없애줄 필요가 없습니다. 문자 자체를 없애기 보다는, 모든 e 문자를 커서가 무조건 거쳐야 한다고 마크해놓은 후, 해당 문자에 들어갔을 때 x 키를 누름으로써 (지우지 않았지만) 사실상 지웠다고 판단해 주어도 됩니다. 이러한 단순화를 한다고 답이 바뀌지는 않지만, 문자열 상 문자를 변형할 필요가 없어서 유리합니다.

더 나아가서, 문자열 자체에서 e의 존재 자체를 지워버릴 수 있습니다. 문자 e를 지우기 위해서는, 이의 오른쪽에 있는 문자를 거쳐야만 합니다. 이 논리를 더 발전시키면, 연속된 e 문자들을 지우기 위해서는 이 연속된 문자들의 오른쪽에 있는 하나의 문자를 무조건 방문해야 하고, 또한 방문하면 이 연속된 문자들을 쉽게 지울 수 있습니다. 그림으로 표현하면 대략 다음과 같습니다.

ccbeeeeebbb <- 원래 상황 (무조건 거쳐야 하는 문자를 마크)

ccbeeeeebbb <- b를 거쳐 연속 구간의 가장 왼쪽 e를 도달

ccbbbb <- x를 연타

이제 문제에서 문자 e와 동작 x를 완전히 지우고, f / h 동작, 그리고 무조건 지나야 하는 문자의 리스트만 가지고 있어도 문제를 풀 수 있습니다. 다음과 같은 Lemma를 구성할 수 있기 때문입니다.

Lemma 2. 변형된 문제의 답 + 2 * (원래 문자열의 e의 개수) 가 변형 전 문제의 답과 동일하다.

이제 지금까지 만든 관찰을 통해서 동적 계획법을 시도합니다. 어떻게 동적 계획법 상태를 정의하느냐가 문제의 핵심으로, 상태를 정의하는 방법에 따라서 동적 계획법 자체가 불가능할 수도 있고, 느린 시간 복잡도가 나올 수도 있습니다.

가장 직관적인 방법은 커서의 위치를 따라가는 것이지만, 여기서 사용하는 방법은 커서의 위치와 관계없이 왼쪽부터 오른쪽으로 순서대로 커서의 경로를 만들어 나가는 것입니다. 점프가 되는 형태를 보면, 임의의 두 문자 사이는 h로 움직여지거나 움직여지지 않는데, 그렇지 않은 상태에서는 왼쪽 -> 오른쪽 점프 정확히 한번 만이 존재하고, 그런 상태에서는 h의 오른쪽으로 오는 점프, 그리고 h의 왼쪽에서 탈출하는 점프 두가지가 존재합니다. 동적 계획법의 상태는 고로:

$dp1(x, C)$ : 현재 x번 문자와 x+1번 문자 사이를 h로 건너지 않으며, fC라는 키워드로 건너뛰고 있는 상황

$dp2(x, COUT, CIN)$ : x번 문자와 x+1번 문자 사이를 h로 건너는 상태에서, 두 개의 점프가 가로지르고 있는데, 이 중 한쪽은 fCIN 키워드로 h의 오른쪽 구간 끝을 향해 도착하며, 다른 한쪽은 fCOUT 키워드로 h의 왼쪽 구간 끝에서 출발.

이들의 상태 전이는 구간이 끝나고 시작할 수 있는 몇가지 케이스들을 고려하면 찾을 수 있습니다. 케이스가 약간 많은 편이니 신중하게 구현해야 합니다. 각 상태 전이 개수는 $x$ 하나당 전체 $O(C^2)$ 로, 시간 복잡도는 $O(NC^2)$ 가 됩니다. $C = 10$ 이라 시간 안에 충분히 통과합니다.