Codeforces Round #788 (Div. 2)

A. Prof. Slim

code

1) 문제 설명

길이 10,000 이하의 숫자로 이루어진 배열이 주어질 때,

부호가 서로 다른 두 숫자를 골라, 수 숫자의 부호를 바꿀 수 있다.

이 과정을 여러 번 반복해서 배열을 정렬할 수 있는지 물어보는 문제이다.

2) 알고리즘

먼저 배열에 음수의 개수가 \( k \) 개라 하자.

배열의 모든 숫자에 절댓값을 취하고, 배열 앞의 \( k \) 개의 수에 -1을 곱해준다.

그 후 배열이 정렬되어 있는 지 확인하면 된다.

B. Dorms War

code

1) 문제 설명

문자열 \(s\)와 특별한 문자 \(c\)가 \(k\) 개 주어진다.

이때 아래 작업을 진행해서 \(s\)의 문자열 중 일부 문자를 지운다.

 

1. 문자열 \(s\)에서 특별한 문자에 해당하는 모든 위치 \(i\)를 찾는다.

2. \(i \ge \)인 모든 \(i\)에 대해 \(i-1\) 번째 글자를 지운다. 이때, \(i-1\) 번째 글자가 특별한 문자라도 지운다.

 

위 작업을 진행할 때, 아무 글자도 지워지지 않는다면 에러가 발생한다.

에러가 발생하기 직전까지 작업을 진행하면, 총 몇 번 작업을 진행하는 지 물어보는 문제이다.

2) 알고리즘

먼저 vector에 특별한 문자의 위치를 모두 저장한다. 이 vector는 앞의 문자를 지우는 특별한 문자들의 위치를 저장한다. 매 작업을 진행할 때마다 vector를 아래와 같이 업데이트한다.

 

vector에 \(n\)개의 원소가 존재한다고 하자.

그렇다면 한 번 작업을 진행하면 \( i (1\leq i \leq n) \) 번째 원소는 숫자가 \(i\)만큼 감소한다. 자신 앞에 있는 문자가 총 \( i \) 개 사라지기 때문이다.

또한 vector에 동일한 숫자가 있다면, 특별한 문자가 다른 특별한 문자를 지운 경우이므로, 하나만 남기고 vector에서 제거하면 된다.

마지막으로, vector의 첫 번째 원소가 0이면 첫 번째 원소를 제거한다. 맨 처음에 있는 특별한 문자는 다른 문자를 제거하지 못하기 때문이다.

 

vector가 빌 때까지 위 작업을 반복하면 된다.

위 과정을 효율적으로 구현하면 작업의 시간복잡도를 \(O(제거한 문자)\)로 구현할 수 있고,

따라서 작업에 에러가 발생할 때까지 작업을 진행하는 알고리즘의 시간복잡도는 \(O(|s|)\)이다.

C. Where is the Pizza?

code

1) 문제 설명

길이가 \( n \)인 두 순열 \(a, b\)가 주어진다. 이때, 새로운 순열 \(c\)를 아래의 조건을 만족해서 구성하는 경우의 수를 구하는 문제이다.

모든 \( i \)에 대해 \( c_i = a_i \space or \space c_i = b_i) \)를 만족해야 한다.

 

2) 알고리즘

간단한 관찰부터 진행해보자.

예를 들어, 카드가 \( a = [1, 2, 3] \), \(b = [3, 1, 2] \) 이렇게 존재한다고 하자.

그렇다면, \( c [1] \) 값을 결정하면, \( c[2], c[3]\) 값도 정해진다.

\( c [1] = 1\)로 고정하면, \( c[2] = 2, c[3] = 3\) 으로 정해지고,

\( c[1] = 2\)로 고정하면, \( c[2] = 1, c[3] = 2\) 로 정해진다.

왜 값이 정해지는 지를 살펴보면, \(c [j], j \neq i\)에서 \( a[i], b[i]\) 중 하나를 사용한다면, \( c[i] \)는 \( c[j] \)가 사용하지 않은 하나를 정해야 하기 때문이다.

 

이를 그래프를 이용하여 표현하자.

1부터 \( n \)까지 총 \( n \) 개의 노드를 가지고, 모든 \( i \)에 대해 간선 \( (a [i], b [i]) \)를 가지는 무향 그래프를 생성하자.

그렇다면 한 component에 있는 노드 중 하나의 값을 결정하면 그 component의 나머지 값들도 전부 결정된다.

이때, 우리가 만든 그래프는 단순 사이클로만 이루어져 있다.

따라서 이 그래프에서 단순 사이클의 길이가 2 이상인 사이클의 개수, \( k \)를 구하면

우리가 구하고자 하는 경우의 수는 \( 2^k \)이 된다.

D. Very Suspicious

code

1) 문제 설명

무한히 큰 벌집 모양의 그림이 있다. 이때, 무한한 선을 0도, 120도, 240도, 360도 방향으로 몇 개 그으면 삼각형이 생긴다.

삼각형을 \( n \) 개를 만들고 싶다면, 선을 최소 몇 개 그어야 하는지 물어보는 문제이다.

2) 알고리즘

만약 선이 \( k \) 개가 있다면 삼각형을 몇 개 만들 수 있는지 계산해보자.

먼저 0도, 120도, 240도 방향의 선의 개수를 각각 \( k_1, k_2, k_3\) 라 하자.

0도와 120도 선만 관찰해보면, 두 선의 교점에서 2개의 삼각형이 생기는 것을 볼 수 있다. 또한 삼각형은 두 선의 교점에서만 생긴다.

따라서 0도와 120도 선이 교차하여 생기는 삼각형의 개수는 \( 2 k_1 k_2\) 이다.

이는 0도와 240도, 그리고 120도와 240도 선의 교점에서도 성립된다.

따라서 총삼각형의 개수는 \( 2 (k_1 k_2 + k_2 k_3 + k_3 k_1) \)이다.

이 값을 최대화하기 위해서는 \( k_1 = k_2 = k_3 = \frac {k}{3} \) 이 성립해야 한다.

물론 선의 개수는 자연수이니, 나누어 떨어지지 않아 남는 선은 아무 데나 추가해주면 된다.

 

이제 선의 개수가 주어질 때 만들 수 있는 최대 삼각형의 개수를 구할 수 있다.

따라서 삼각형의 개수가 주어질 때 만들 수 있는 최소 선의 개수는 이분 탐색으로 구할 수 있다.

E. Hemose on the Tree

code

1) 문제 설명

정점이 \( n \) 개인 트리가 주어진다. 이때 n은 \( 2^p\) 꼴이다.

이 트리의 정점과 간선에 숫자를 \( 1 \)부터 \(2n-1 \)까지 중복되지 않게 할당한다.

트리의 루트를 원하는 것으로 하나 정하고, 루트에서 정점 또는 간선까지의 비용을

루트에서 정점 또는 간선까지 가는 동안 거치는 모든 정점과 간선에 할당된 숫자들의 XOR 값으로 정의한다.

그렇다면 루트에서 모든 정점과 간선까지의 비용의 최댓값이 나올 것이다.

우리는 이 최댓값을 최소한으로 만들고 싶다. 최소화하기 위해서는 정점과 간선에 숫자를 어떻게 할당해야 하는 지를 출력해야 한다.

2) 문제 관찰

쉽게 \(n = 16\) 이라 가정하고 문제를 관찰해보자.

이제 임의로 1 ~ 31까지의 숫자를 할당한다. 그렇다면 비용의 최댓값을 16 미만으로 줄일 수 있을까?

물론 불가능하다. 일단 16에 해당하는 bit는 4번째 bit이고, 1 ~ 31 숫자에는 4번째 bit가 켜진 숫자가 16개나 존재한다.

그렇다면 트리에는 루트에서 특정 정점 또는 간선까지 4번째 bit가 켜진 숫자를 1개만 포함하는 경로가 무조건 하나는 존재한다는 뜻이다.

따라서 비용의 최댓값은 16 미만으로 줄일 수 없다. 따라서 비용의 최댓값은 적어도 16 이상이다.

이를 일반화하면 비용의 최댓값은 적어도 \( n \) 이상이다.

만약 비용의 최댓값을 \( n \)으로 정할 수 있는 알고리즘이 존재한다면, 이 알고리즘은 비용의 최댓값을 최소화하는 알고리즘이라 할 수 있다.

3) 알고리즘

여기서도 \(n = 16\) 이라고 가정하고 문제를 풀어보자.

비용의 최댓값이 16이라는 의미는 4번째 bit가 켜져 있다면 나머지 모든 bit는 꺼져있고, 4번째 bit가 꺼져있다면 나머지 모든 bit는 어떻게 되든 상관이 없다.

 

루트에서 특정 정점까지의 비용이 16이라고 하자. 적당한 16 미만의 숫자 \(x\)를 골라 그 아래의 간선에 16 + \(x\), 그리고 그 간선 아래의 노드에 \(x\)를 할당하면 루트에서 간선까지의 바용은 \(x\), 그리고 루트에서 간선 아래 노드까지의 비용은 0이 된다.

 

마찬가지로, 루트에서 특정 정점까지의 비용이 0이라고 하자. 적당한 16 미만의 숫자 \( x\)를 골라 그 아래의 간선에 \( x \), 그리고 그 간선 아래의 노드에 \( 16 + x \)를 할당하면 루트에서 간선까지의 비용은 \(x\),  그리고 루트에서 간선 아래 노드까지의 비용은 16이 된다.

 

루트를 제외하면 간선과 그 간선 아래에 있는 정점 쌍은 총 15개이다. 따라서 이 15개의 쌍에 대해 \( (x, 16 + x) \)를 할당해주면 된다. 만약 간선 위의 정점까지의 비용이 16이면 간선과 그 아래 정점에 \( (16 + x, x) \)를, 간선 위의 정점까지의 비용이 0이면 간선과 그 아래 정점에 \( (x, 16 + x) \)를 할당하면 된다. \( x \)는 서로 다른 1 이상 15인 수를 선택해서 15개 쌍에 할당한다.

 

마지막으로 루트에 n을 할당한다. 루트 정점의 높이를 0이라 하면,

높이가 짝수인 정점까지의 비용은 n, 높이가 홀수인 정점까지의 비용은 0이 된다. 이렇게 할당하면 모든 정점까지의 비용은 0 또는 16이고, 모든 간선까지의 비용은 1이상 15 이하의 비용이다.

 

따라서 이를 일반화하여 구현하면, 모든 비용이 n 이하가 되도록 정점과 간선에 숫자를 할당할 수 있다.

 

F. Jee, You See?

code

1) 문제 설명

숫자 \(n, L, R, z\)가 주어진다. \( n \)은 1,000 이하의 자연수이고, \(L, R, z\) long long 범위의 매우 큰 수이다.

이때, 아래 조건을 만족하는 길이 \( n \)인 배열의 개수를 출력하는 문제이다. (\(\otimes\)는 XOR이다.)

1. \( L \leq a_1 + a_2 + \ldots + a_n \leq R \)

2. \(a_1 \otimes a_2 \otimes \ldots \otimes a_n = z\)

2) 알고리즘

먼저 \(dp(l, r, k)\)를 0번째 bit부터 \(k\) 번째 bit까지 사용하여 \(l\) 이상 \(r\) 이하가 되도록 하고 XOR이 \(z\)가 되도록 하는 배열 \(a\)의 개수로 정의하자.

그렇다면 점화식은 아래처럼 구할 수 있다.

$$ dp(l, r, k) = \left\{\begin {matrix}
\sum_{i} dp(l-(2i+1) \times 2^k, r - (2i+1) \times 2^k, k - 1) \times nCi,
\mathrm {if \space z \space \& \space 2^k \space is \space not \space zero}
 \\
\sum_{i} dp(l-2i \times 2^k, r - 2i \times 2^k, k - 1) \times nCi,
\mathrm {otherwise}
\end {matrix}\right. $$

수식의 의미는 간단하다. \( k \) 번째 bit만 결정해보자.

만약 \( z\)의 \(k\) 번째 bit가 켜져있다면, 배열의 \( n\)개의 숫자 중 홀수 개의 숫자만 \(k\)번째 bit가 켜져있어야 하고, 반대의 경우에는 짝수 개의 숫자만 bit가 켜져있어야 한다.

만약 \(k\)번째 bit를 \(i\) 개만큼 키면, 배열 숫자의 총합이 \(i \times 2^k \) 만큼 증가하므로, 목표 범위인 \(l, r\)을 \(i \times 2^k \)만큼 감소시킨다. 그리고, \(n\) 개 중,  \(i\) 개의 bit를 켜는 경우의 수는 \(nCi\)이다.

따라서 \( z\)의 \(k\) 번째 bit를 \(i\) 개 키면 위 조건을 만족하는 배열의 경우의 수는 \( dp(l-i \times 2^k, r - i \times 2^k, k - 1) \times nCi \)이고, \(z\) 값에 따라 가능한 \(i\)를 홀짝으로 나누면 위 점화식을 얻을 수 있다.

 

그냥 보면 \(l, r\)의 범위가 매우 크기에 시간과 공간 복잡도가 매우 크다고 생각할 수 있다. 하지만 특정 상황의 결과를 처리해두면, 계산해야 할 dp의 개수가 매우 줄어든다.

먼저 \(dp(l', r', k+1)\) 값을 계산하기 위해 필요한 \(dp(l, r, k)\)가 몇 개인지를 생각해보자.

\(l, r\)이 아예 불가능한 경우 거나, 나머지 \( k\) 개의 bit를 어떻게 설정해도 범위 안에 들어올 정도로 매우 넓은 범위이면 \(2^{kn}\)으로 바로 구할 수 있다.

또한 dp 식을 계산하는 동안 \(r - l\) 값은 변하지 않는다. 그리고, \(dp(l, r, k)\)에 들어오는 \( l\) 값은 \(L - i2^{k+1}\) 꼴임을 위 점화식에서 유추할 수 있다. 따라서 실제로 계산해야 할 \(dp(l, r, k)\)의 개수는 \(O(n)\) 정도밖에 되지 않는다.

 

그러므로, dp값을 배열이 아니라 map 등의 자료구조를 사용하여 저장하고, 점화식을 풀면 문제의 답을 구할 수 있다.