CodeTON Round 3

A. Indirect Sort

code

문제 설명

길이가 \(n\)이고 1부터 \(n\)까지 한 번만 등장하는 배열이 입력으로 주어진다.

\(1\le i < j < k \le n\)인 세 정수를 골라 아래와 같은 연산을 진행한다.

만약 \(a_i > a_k\)이면 \(a_i\)에 \(a_j\)만큼 더하고, 그렇지 않다면 \(a_j\)와 \(a_k\)를 swap한다.

여러 번의 연산을 통해 배열을 오름차순으로 정렬할 수 있는지 여부를 출력해야 한다.

알고리즘

이 문제는 배열의 첫 번째 원소에 집중하면 빠르게 풀 수 있다.

먼저 배열의 첫 번째 원소가 1이라 가정하자. 그렇다면  \(i = 1\)을 고르면, 두 번째 원소부터 마지막 원소까지 원하는 대로 변경할 수 있어 무조건 바꿀 수 있다.

하지만 첫 번째 원소가 1이 아니라 가정하자. 그렇다면, 값이 1인 원소가 있을 텐데 이 값보다 작은 원소는 없으므로, 이 값을 1보다 키울 수 없다.

그렇다면 첫 번째 원소보다 작은 1이라는 원소가 존재하는데, 이 1을 맨 앞으로 가져올 방법이 없다. 따라서 정렬이 불가능하다.

즉, 맨 첫 번째 수가 1인지 아닌지 여부를 출력하면 된다.

 

B. Maximum Substring

code

문제 설명

0과 1로만 이루어진 문자열 \(s\)가 주어진다.

문자열 \(t\)에 대해 \(t\)에서 0의 개수와 1의 개수를 각각 \(x\), \(y\)라 하면, 이 문자열의 비용은

\(x\)가 0이면 \(y^2\), \(y\)가 0이면 \(x^2\), 둘 다 0보다 크면 \(xy\)로 정의된다.

이제 문자열 \(s\)의 부분 문자열 중 비용이 최대인 부분 문자열의 비용을 출력해야 한다.

알고리즘

단순히 모든 부분 문자열을 보려 하면 \(O(n^2)\)이므로 시간 초과가 발생한다. 따라서 시간 복잡도를 줄이기 위해 문제를 다른 관점으로 봐야 한다.

먼저 문자열의 비용이 총 세 종류로 정의가 된다. 하나는 \(x\)가 0인 경우, 하나는 \(y\)가 0인 경우, 다른 하나는 둘 다 양수인 경우로 나눠진다. 문자열의 비용은 이 세 종류 중 한 종류에 속한다.

따라서 부분 문자열의 비용의 최댓값을 아래와 같이 쪼개서 생각할 수 있다.

1. \(x\)가 0인 경우 중 비용의 최댓값

2. \(y\)가 0인 경우 중 비용의 최댓값

3. \(x\), \(y\)가 모두 양수인 경우 비용의 최댓값

 

위 세 경우의 최댓값을 각각 구하고, 위 세 값 중 가장 큰 값이 이 문제의 정답이 된다.

1번과 2번의 경우는 \(O(n)\)으로 쉽게 구할 수 있다. 가장 긴 연속된 0 또는 1의 길이를 계산하면 된다.

3번의 경우는 부분 문자열이 문자열 전체인 경우에 해당한다. 따라서 전체 문자열 \(s\)의 \(x\)와 \(y\)를 구한 뒤 둘을 곱해주며 된다.

위 과정을 통해 \(O(n)\) 안에 정답을 계산할 수 있다.

 

C. Complementary XOR

code

문제 설명

0과 1로 이루어지고 길이가 \(n\)으로 같은 두 문자열 \(a\), \(b\)가 주어진다.

이제 \(L, R\)의 두 정수를 정해 \([L, R]\) 구간에 있는 a의 값들을 1과 XOR 하고, 이 구간밖에 있는 b의 값들을 1과 XOR 한다. 

위 연산을 통해 \(a\), \(b\)를 모두 0으로 만들 수 있는지 여부를 출력하고, 가능하다면 \(n+5\)번 이내의 연산을 사용해 실제로 모든 값을 0으로 만들어야 한다.

알고리즘

먼저 언제 모든 값들을 0으로 만들 수 없는지를 구해야 한다.

\(a \oplus b\) 값을 생각해보자. 먼저 두 문자열을 모두 0으로 만들게 되면, \(a \oplus b\)는 0이 된다. 또한, 연산을 한 번 진행할 때마다 \(a \oplus b\)의 모든 값들이 1과 XOR된다. 따라서 \(a \oplus b\)를 0으로 만들기 위해서는 최소한 \(a \oplus b\)가 모두 0이거나 모두 1이어야 한다.

 

이제 \(a \oplus b\)가 모두 0이거나 모두 1인 경우를 생각해보자. 먼저 연산을 한 번 적용할 때마다 \(a \oplus b\)의 값이 변하기 때문에 연산을 진행한 횟수를 기록해서 \(a \oplus b\)의 값을 계산할 수 있다.

일단 \(a\)를 모두 0으로 만들어보자. 이는 매우 간단하게, \(a\)에서 1인 index를 \(i\)라 하면, 모든 \(i\)에 대해, 연산 \([i, i]\)를 적용하면 \(n\)번의 연산 안에 \(a\)가 모두 0이 된다.

이제 \(b\)의 값들을 생각해봐야 하는데, 일단 \(a\)가 모두 0이므로, \(a \oplus b\)의 값이 곧 \(b\)이므로, \(b\)는 모두 0이거나 모두 1이다.

\(b\)가 0인 경우는 계산을 더 할 필요가 없으므로 \(b\)가 1인 경우를 생각해보자. 이 경우에는 총 3번의 연산을 취해 \(b\)의 모든 값들을 0으로 만들 수 있다. 바로 \([1, 1], [2, n], [1, n]\)의 세 연산을 취하면 된다. 이 연산을 취하면 \(a\)의 모든 값들이 두 번 XOR되고, \(b\)의 모든 값들은 한 번만 XOR되어 결과적으로 \(b\)의 값들만 모두 XOR연산을 한 게 된다.

 

따라서 위 알고리즘을 사용하면 \(n+3\)번의 연산 안에 문제를 풀 수 있다.

 

D. Count GCD

code

문제 설명

값이 1이상 \(m\)이하인 정수이고, 길이가 \(n\)인 배열 \(a\)가 입력으로 주어진다.

이제 아래 조건을 만족하면서 가능한 배열 \(b\)의 개수를 구해야 한다.

1. \(b\)의 모든 값들은 1이상 \(m\)이하이다.

2. \(\gcd(b_1, b_2, ...,b_i) = a_i\)

알고리즘

먼저 \( \gcd(b_1, ..., b_i) = \gcd(a_{i-1}, b_i) = a_i \) 인 것을 관찰하면, 각 \(b_i\)에 대해 경우의 수를 독립적으로 계산할 수 있다.

일단 위 식에서 \(a_{i-1}\)은 \(a_i\)의 배수가 되어야 한다는 것을 볼 수 있다. 그렇지 않다면 경우의 수가 0이 된다.

먼저 \(a_1\)의 소수인 인수를 모두 찾는다. 이 개수는 최대 9개를 넘지 않는다.

이제 \(a_i\)의 인수 중 소수인 인수는 이 9개에 대해서만 검사해주면 된다.

이를 이용하면 \(b_i\)가 \(a_{i-1}\)의 배수이면서 \(a_i\)와 서로소인 수의 개수를 포함-배제 원리를 이용해서 계산해주면 된다.

E. Bracket Cost

code

문제 설명

괄호 문자열이 존재한다. 이 괄호 문자열의 비용을 유효한 괄호 문자열로 바꾸기 위해 수행해야 하는 연산의 최소 횟수로 정의한다. 가능한 연산은 두 가지가 있다.

1. 주어진 문자열 중 부분 문자열을 한 칸 오른쪽으로 쉬프트한다.

2. 원하는 위치에 ( 또는 )를 추가한다.

 

길이가 \(n\)인 문자열이 입력으로 주어진다. 가능한 \(\frac{n(n+1)}{2}\)개의 모든 부분 문자열의 비용의 합을 출력해야 한다.

 

알고리즘

많은 관찰이 필요하다.

가장 먼저 관찰해야 할 사실은 주어진 문자열의 비용을 어떻게 계산하느냐이다.

먼저 괄호 문자열 중 '()'인 부분을 모두 제거해보자. 그렇다면 ')))((((('와 같은 꼴이 될 것이다. 이 꼴에서는 1번 연산을 적용해서 '))((((()' 와 같이 '()'인 것을 하나 만들고 제거해서 '('와 ')'를 하나씩 제거할 수 있다. 이렇게 계속 하나씩 지우다 보면 '('와 ')' 중 한 종류만 남게 된다. 이는 2번 연산을 이용해서 모두 제거할 수 있다.

위 내용을 정리해보면, '()'인 부분을 모두 없애고, 남는 문자열에 대해 \(\max\)('('의 개수, ')'의 개수\()\)가 문자열의 비용이라는 것을 관찰할 수 있다. 일단 '()'을 고려하지 않고 모든 부분 문자열에 대해 max값의 합을 구하는 과정을 생각해보자.

 

일단 빈 배열을 하나 만든다. 그리고, 주어진 문자열의 모든 글자에 대해 아래 연산을 진행한다.

1. 먼저 배열의 맨 끝에 0을 추가한다.

2. 만약 글자가 '('면 배열의 모든 값에 1을 추가하고, ')'면 배열의 모든 값에 -1을 추가한다.

예를 들어 ')()('라면, 배열은 \([-1], [0, 1], [-1, 0, -1], [0, 1, 0, 1]\) 과 같이 변하게 된다.

 

여기서 \(j\)번째 배열의 \(i\)번쨰 값은 \([i, j]\) 구간에서 '('의 개수에서 ')'의 개수를 뺀 값이 된다.

이제 배열의 값들을 이용해서 max값의 합을 계산할 수 있다.

먼저 배열이서 0 이상인 값들은 '('의 개수가 최소 ')' 개수와 같거나 더 많다는 뜻이다. 이 상황에서 '('가 추가된다면 max('(', ')')의 값은 1만큼 증가한다. 하지만 0 미만인 값들은 max값이 유지된다. 따라서 위 연산을 진행할 때, max값의 합이 얼마나 변하는지 알 수 있다. 이를 이용하면 max값의 합을 \(O(NlgN)\)안에 구할 수 있다.

 

이제 위에서 생략했던 '()'를 고려해보자. 먼저, 원래 문자열에서 '('와 대응이 되는 ')'의 위치를 모두 매칭한다. 이 위치를 \(L, R\)이라 하자. 그렇다면 정답은 총 개수에서 \(L \times (n-R)\)개 만큼 줄어든다. 자세한 구현은 위 링크의 코드에 있다.