RUN@KAIST 8/24 방학 연습 풀이

1. Lazy Spelling Bee

각각의 스텝에서 선택할 수 있는 문자의 개수는 최대 3가지다. 이 중 서로 다른 문자의 개수가 우리가 이번에 택할 수 있는 경우의 수다. 문제를 풀 때는, 스텝을 순서대로 처리한다. 각 스텝마다 선택할 수 있는 서로 다른 문자의 개수를 계산한 후, 이 문자의 개수를 경우의 수에 곱해주면 된다.

2. Sums of Sums

쿼리 개수가 많지 않으니 각각의 쿼리를 독립적으로 보자. 일단. 구간 $[L, R]$ 에 있는 수의 합를 계산한다고 하면 복잡하니, 구간 $[1, R]$ 에 있는 수의 합을 계산하고, $[1, L-1]$에 있는 수의 합으로 빼주는 것이 생각하기 편하다. 고로, 구간 $[1, X]$ 에 있는 부분 합들의 sum을 계산하는 문제를 풀면 된다.

$X$번째까지의 합을 더하는 문제는 막막해 보이니 조금 더 쉬운 문제를 풀어보자. 합이 아니라 $X$번째 수가 무엇인지는 계산할 수 있을까? 이는 이분 탐색과 two pointers로 할 수 있다. 왜냐하면, 부분 합이 $S$ 이하인 구간의 개수를 $O(N)$에 셀 수 있기 때문이다. 각각의 위치 $i$에 대해서, $Sum[i, j] \leq S$ 를 만족하는 최대 $j$를 구할 수 있다. 흔히 inchworm이라 불리는 방법을 사용해서, 1에서 $Sum[1, j] \leq S$일 때까지 j를 늘려주고, 2에서는, 1에서 찾았던 $j$에서 시작하고 계속 늘려주고, 3에서도 ... 이를 반복하면 되기 때문이다. $S$ 이하인 구간의 개수는 $X$ 이상이며, $S$ 미만인 구간의 개수는 $X$ 미만이라면, $X$번째 수는 $S$이다. 고로, 답에 대한 이진 탐색처럼 $S$에 대해서 이진 탐색을 하면 된다.

이를 합에 대한 문제로 응용할 수 있을까? $S$가 주어졌을 때, 부분 합이 $S$인 구간의 개수 뿐만 아니라 그러한 구간들의 총 합까지 알 수 있다. 위와 똑같이 inchworm을 쓰면서 $i$에 대응되는 $j$를 찾으면, 부분합 배열을 $S_i$라 할 때 $(S_i - S_{i-1}) + (S_{i+1} - S_{i-1}) + \cdots + (S_j - S_i)$ 의 합을 구하면 된다. 이는 $S$에 대한 부분합 배열인 $SS_i$를 또 구하면 $O(1)$에 찾을 수 있다. $S$ 이하의 구간의 개수 뿐만 아니라 총합까지 알 수 있으니, 이분 탐색으로 $X$번째 수를 찾음과 동시에 문제 전체를 해결할 수 있다.

이렇게 문제를 해결하면 $O(TQNlg(N * a_i))$ 에 문제를 해결할 수 있다. 구글 코드잼이라 그렇게 큰 TC가 전부 들어오는 것 같지는 않고, 이렇게 짜면 AC가 나온다.

3. Breed Assignment

주어진 제약 조건들을 간선으로 본다면, 이 문제는 3-coloring 문제로 효율적인 풀이가 없는 것이 알려져 있다. 고로 지수 시간 풀이가 우리가 찾을 수 있는 최선이다. 이 문제는 $3^N$개의 모든 경우를 단순히 테스트 하더라도, 백트래킹 과정에서 가지를 적절히 쳐 주면 충분히 시간 안에 나오는 문제이다. 하지만, 조금 더 빠른 $O(2^N * N^2)$ 풀이를 소개하려고 한다.

먼저, $2^N$ 가지 경우를 모두 돌며 3번 타입의 소의 부분집합 $S$을 정해준다. 이렇게 될 경우, 부분집합 $S$ 내부에 있는 두 소에 대한 간선들은 모두 같은 색을 표시해야 하고, 부분집합 안에 있는 소 + 부분집합 밖에 있는 소를 잇는 간선은 다른 색을 표시해야 한다. 이를 간선 집합을 순회하면서 확인해 주자. 이제 $S$ 내부에 있는 소들을 1번 / 2번 타입으로 정하는 경우의 수를 세야 한다. $S$ 외부에 있는 두 소를 잇는 간선들을 모두 더해주면, "두 색이 같아야 한다" / "달라야 한다" 형태의 간선들이 주어진다. 이는 일반적인 이분 그래프 색칠 문제의 변형으로, 각각의 컴포넌트에서 아무 정점에 아무 색을 칠해 준 후, 다른 정점들을 정해지는 대로 칠한 후 모순이 있는지 보는 식으로 해결할 수 있다. 모순이 없다면, 해당 그래프의 컴포넌트마다 두 가지의 경우의 수가 있다. 고로 2 ^ (컴포넌트 수) 가 답이 된다.

4. Room Assignments

문제를 간단히 하자. $N$개의 정점과 $N-1$개의 간선이 있을 때, 우리는 하나의 간선을 추가하여, 각각의 정점과 간선이 완벽 매칭을 이룰 수 있게 해야 한다. (즉, 각각의 간선에 서로 다른 정점이 배정되며, 배정된 정점은 간선의 양 끝 점 중 하나이도록) 가능한 여러 경우 중에서는, 매칭의 기댓값을 최소화해야 하는데, 일단 이것은 무시하자.

먼저, 하나의 간선을 어떻게 추가할 수 있을지 살펴보자. $N$개의 정점과 $N-1$개의 간선이 있으면 일반적으로 트리지만, 연결 그래프라는 조건이 없기 때문에 실제 트리는 아니다. 각각의 연결 컴포넌트에 대해서 어떠한 경우들이 있을 수 있는 지 살펴보자.

 * Case 1. 간선의 개수가 정점의 개수와 같을 경우. 사이클 하나에 트리가 매달려 있는 형태이다. 트리의 경우에는 degree 1인 정점이 매칭해야 할 간선이 정해지기 때문에, 결국 사이클 안에서 각 정점이 원하는 간선들을 순서대로 매칭시키면 항상 매칭이 존재함을 알 수 있다.

 * Case 2. 간선의 개수가 정점의 개수보다 적은 트리. 이러한 컴포넌트가 있다면, 무조건 이 트리에 에지를 추가해야 매칭이 존재한다. Case 1에서 봤다 시피 어떻게 에지를 추가해도 매칭은 존재하니, 에지는 마음대로 추가하면 된다.

 * Case 3. 간선의 개수가 정점의 개수보다 많은 컴포넌트. 이 컴포넌트는 가만히 두면 절대 매칭이 안 되기 때문에 새로 에지를 추가해서 다른 연결 컴포넌트를 끌어와야 한다. 사이클을 끌고 온다면, 간선이 정점 개수보다 많이 늘어나기 때문에 오히려 좋지 않다. 트리를 끌고 오면, 간선의 개수와 정점의 개수가 똑같이 늘어나서 아무 의미가 없다. 고로, 이러한 컴포넌트가 존재한다면 절대 답이 존재하지 않는다.

Case 3이 없다면, 그래프의 총 정점의 개수가 간선보다 1개 많기 때문에 트리가 1개, 나머지는 사이클들의 집합이 된다. 우리가 할 수 있는 것은 두가지인데, 트리 안에서 에지를 잇거나, 트리와 사이클을 잇는 것이다.

이제 cost를 최대화하는 방법을 생각해 보자. 결국 어떻게든 트리에서 정점을 이어서, Case 1과 같은 그래프를 만들 것이다. 이 때의 그래프는 사이클 하나에 트리가 매달려 있는 형태인데, 사이클에 속하는 간선들은 양 옆에 있는 어떤 정점이든 매칭시킬 수 있다. 하지만, 트리에 속하는 간선들은 루트의 아래쪽 정점과 매칭이 되는 것이 결정된다. 

고로, 트리 안에서 에지를 이을 경우, 에지의 양 끝 점의 가중치 평균이 기댓값이 될 것이고, 사이클과 트리를 이을 경우, 트리쪽에 속하는 끝 점이 기댓값이 될 것이다. 사이클과 트리를 이을 경우에는, 가중치가 최대인 정점을 다른 사이클 아무거나와 이어주면 되고, 트리와 트리를 이을 때는 첫번째 최댓값을 가지는 정점과 두번째 최댓값을 가지는 정점을 이으면 된다.