plast / 코딩공부

C. Complementary XOR

0과 1만으로 이루어진 n(2 ≤ n ≤ 2e5)자리 문자열 a, b가 있습니다. 다음과 같은 연산을 최대 n + 5번까지 했을 때 모든 문자열을 0으로 만들 수 있는지 판단하세요.
연산 (l, r) : i = l ~ r까지의 문자열 a의 0과 1을 전부 반전시킵니다. 그리고 1 ~ l - 1, r + 1 ~ n까지의 문자열 b의 0과 1을 전부 반전시킵니다.

이 연산 (l, r)은 문자열 a는 i = l ~ r까지는 반전시키고 문자열 b는 i = l ~ r까지를 제외한 전부를 반전시킨다. c라는 것을 정의해 c[i] = (a[i]와 b[i]가 같다면 1, 다르다면 0) 이라고 할 때, 연산은 어떤 구간을 잡아도 항상 c를 1 ~ n 까지 전부 반전시킴을 알 수 있다. 즉 처음부터 c[i]가 모두 같지 않다면 이 연산만으로는 a와 b를 전부 0으로 만들수가 없다.

그 뒤에는 평범하게 a의 연속된 1 무리들을 전부 0으로 변환해주면 된다. 그러면 b는 전부 0이거나 전부 1이 되는데, 전부 1이 될 때에는 (1, n), (1, 1), (2, n) 순으로 3번의 연산을 더 거치면 b까지 전부 0으로 바꿔주는 것이 가능하다.

이 문제를 풀 때 생각을 잘못해서 몇번 삐끗했다. a를 전부 0으로 만들어도 b가 전부 1이되면 방법이 없을 거라는 생각에 좀처럼 답을 찾지 못했다. 그런데 생각해보면 예제에서 친절하게 '111 111' 을 보여줬기 때문에 이 예제의 해결법을 연관지어서 생각했다면 더 빠르게 풀이를 찾아냈을 것 같다.

D. Count GCD (1800)

n(1 ≤ n ≤ 2e5)개의 숫자로 이루어진 수열 a가 있습니다. 다음과 같은 조건을 만족하도록 b배열을 만들 때, 가능한 가짓수를 구하세요.
- 모든 i에 대해, gcd(b[1], b[2], ... , b[i]) = a[i] 를 만족한다.
- b의 원소는 전부 1 이상 m(1 ≤ m ≤ 1e9) 이하이다.

b[i]로 가능한 숫자가 몇개인지 생각해보자. gcd(b[1], b[2], ..., b[i]) = a[i]의 식에서 시작해, 공약수의 성질을 바탕으로 gcd(a[i - 1], b[i]) = a[i]로 나타낼 수 있다. 이 조건을 만족하기 위해서는 b[i]는 a[i]의 배수이면서 (a[i - 1] / a[i])와 (b[i] / a[i])는 서로소여야 한다. a[i]의 배수인 수의 개수는 m / a[i]로 바로 판단이 가능하고, 서로소인 수의 개수는 포함배제의 원리를 이용해 각 약수를 바탕으로 판단이 가능하다.

안그래도 포함배제의 원리에 대해 공부하고 있었는데 연습 도중 바로 볼 수 있어서 좋았다. 포함배제의 원리를 이용하는 수학문제는 코드포스에서 가장 전형적인 문제 중 하나라고 생각한다.

E. Bracket Cost (2400)

n(1 ≤ n ≤ 2e5)개의 소괄호 "(", ")"만으로 구성된 문자열 a가 있습니다. 해당 문자열의 모든 연속부분문자열에 대해, cost의 합을 구하고 싶습니다. cost는 다음 연산을 최소로 이용해 올바른 문자열로 만들 때, 필요한 최소 연산 수를 의미합니다.
- 연산 1 : 해당 문자열의 아무 연속부분문자열을 선택해, 한 칸씩 왼쪽으로 밉니다. 예를 들어, ")()("을 선택하면 이 부분은 "()()"이 됩니다.
- 연산 2 : 아무 위치에 ")" 혹은 "("을 하나 추가합니다.

연산 1이 무엇인지부터 자세히 관찰해 보자. 예를 들어 연산 1을 할 때 문자열 ")(())("을 선택했다고 치자. 해당 문자열은 "(())()"이 된다. 즉 문자열 S를 선택했을 때 S의 가장 앞 문자를 S의 가장 뒤로 옮기는 행위라고 생각할 수 있다. 따라서 S의 가장 앞 문자만이 영향을 받는다.

이를 바탕으로 아무 문자열의 cost를 구해보자. ")))(("를 생각해 보자. 이 경우 연산1을 적극적으로 활용하는 것이 좋다. 왜냐하면 쌍이 맞지 않은 ")"와 "("를 동시에 쌍을 맞출 수 있기 때문에 연산2를 2번 해야 하는 것을 1번으로 줄일 수 있기 때문이다. 따라서 연산1을 2번 써서 앞쪽의 ")"를 뒤로 적절히 옮겨주고 하나 남은 ")"의 앞에 "("를 연산2로 붙여주는것이 최선임을 알 수 있다. 이를 조금 더 고민해보면 일반적인 cost를 정의할 수 있다. 문자열에서 쌍이 맞지 않은 ")"의 개수를 p, "("의 개수를 q라고 할 때 max(p, q)가 된다.

따라서 이 문제는 p와 q를 빠른 시간에 관리하고 cost의 총합을 한번에 구하는 문제로 바뀐다. 여기서 O(n^2)의 풀이는 쉽게 찾아낼 수 있다. stack을 활용하면 (1, 1)에서 시작해 (1, n)까지의 p, q를 각 차례마다 O(1)에 갱신해줄 수 있어서 총 O(n)이 걸리며, 이를 반복해 (2, 2)에서 시작, (3, 3)에서 시작, ... , 을 반복하면 된다.

하지만 이 방법으로는 O(n^2)에서 더 낮추기 쉽지 않다. O(nlgn)혹은 그 이하로 줄이기 위해서는 반드시 모든 쌍을 전부 돌지 않고 한번에 연산하는 과정이 필요하다. 여기서 p의 특징을 이용할 수 있다. "("을 +1, ")"을 -1이라고 정리한 순열 a가 있을때, 순열 b를 b[i] = a[1] + ... + a[i], 즉 a의 prefix sum이라고 하자. [l, r] 구간에 대해 p는 b[l - 1] - min(b[l - 1], b[l], b[l + 1], ... , b[r])이 된다. 그리고 q는 b[r] - b[l - 1] + p가 된다. (b[r] - b[l - 1]은 "("이 몇개 더 있는지를 알려주므로, 쌍이 맞지 않는 "("은 전체 "("의 개수에서 전체 ")"의 개수를 빼고 쌍이 맞지 않는 ")"의 개수를 더해줘야 한다.) 따라서 cost를 max(b[l - 1], b[r]) - min(b[l - 1] ~ b[r]) 으로 변형할수 있다.

이 값의 총합을 구하는 것은 max(b[l - 1], b[r])항과 min(b[l - 1] ~ b[r])을 나눠서 생각해 볼 수 있다. max(b[l - 1], b[r])의 총합은 펜윅 트리를 이용하거나 정렬을 통해 가장 큰 수부터 순서대로 n, n - 1, n - 2, ... , 0회 나올 것임을 바탕으로 구해줄 수 있다. min(b[l - 1] ~ b[r]) 항의 경우 펜윅 트리 / 스택 / 분할정복 등으로 히스토그램의 최대 넓이 구하는것과 비슷한 방식으로 처리할 수 있다.

필자는 쌍이 맞지 않는 ")"의 개수 = b[l - 1] - min(b[l - 1], b[l], b[l + 1], ... , b[r]) 이라는 접근을 처음 봤는데, 자주 나오는 성질인 것으로 보인다. 꼭 알아둬야 할 것 같다. 그리고 필자가 모든 경우의 총합을 구하라는 유형에 상당히 약한 것 같은데, 연습을 많이 해야 할 것 같다.

F. Majority (2700)

0과 1로 이루어진 수열이 있습니다. 다음 작업을 통해 수열의 모든 부분을 1로 만들 수 있는지 알고 싶습니다:
- 작업 (i, j) (단, i < j) : s[i] = s[j] = 1이고, 2 * (s[i] + s[i + 1] + ... + s[j]) ≥ (j - i + 1) 을 만족할 때, s[i], s[i + 1], ... , s[j]를 모두 1로 바꿉니다.
수열의 길이가 n(1 ≤ n ≤ 5e3)일 때, 만들 수 있는 모든 수열 중에서 모든 부분을 1로 만들수 있는 수열의 개수를 구하세요. 

추가예정 

F1을 못 푼게 너무 아쉬웠다. 충분히 대회 시간 안에 풀 수 있었는데, 접근 과정에서 시간이 오래 끌렸고 구현에서도 실수를 많이 한 탓에 시간이 빠듯했다.

A. Add Plus Minus Sign

0과 1로 이루어진 n(1 ≤ n ≤ 1e3)자리 문자열이 주어집니다. 주어진 숫자들 사이에 +와 -를 넣어서 수식을 만들었을 때, 결과값의 절댓값이 최소가 되게 만들고 싶습니다. 그렇게 되도록 +와 -를 적절히 배치해 결과값의 절댓값을 최소로 만드는 방법 중 아무 한 가지를 출력하세요.

홀짝성을 바탕으로 정답을 쉽게 찾을 수 있다. 1이 홀수개 있다면 어떻게 더하고 빼더라도 최소 1이 되고(반드시 홀수가 되기 때문에), 1이 짝수개 있다면 최소가 0이 될 수 있다. 이를 바탕으로 올바른 답이 나오게 적절히 +와 -를 배치하면 된다.

B. Coloring

총 n(1 ≤ n ≤ 1e9)개의 칸에 m(1 ≤ m ≤ 1e5)개의 색을 칠하려 합니다. 각 색갈별로 칠해야 하는 칸의 개수가 주어졌을 때, 어떤 연속 k개의 구간을 잡아도 k칸이 모두 다른 색깔이도록 칠할 수 있는지 여부를 출력하세요.

우선 다른 색은 신경쓰지 않고 하나의 색만 생각해 보자. 1번째 칸에 색칠을 한다면 k번째 칸까지는 같은 색으로 색칠할 수 없다. 따라서 1, k + 1, 2k + 1, ... 다음과 같이 색칠해 최대 ceil(n / k)회 색칠할 수 있다. 즉, ceil(n / k)보다 많이 칠해야만 한다면 반드시 불가능하다. 또한 정확히 ceil(n / k)회 색칠할 수 있는 개수도 한정되어 있기 때문에 조건을 잘 살펴 가능한지 여부를 따져야 한다.

이 문제는 이번 대회에서 가장 핫한 문제였다. 그 이유는..

프리테스트가 약한 탓에 정확히 ceil(n / k)회 색칠한 경우를 처리하지 않아도 프리테스트가 통과됐기 때문이다.

필자는 우연히 이 문제를 올바르게 접근했는데, 처음에 문제를 잘못 읽어서 (...) 이상한 코드로 한번 틀렸다가 정신 바짝 차리고 꼼꼼히 읽은 덕분에 ceil(n / k) 지점에 대해 발견했던 것 같다. 아니였다면 필자도 똑같이 틀렸을 가능성도 상당히 높았을 것 같다.

C. Ice and Fire

온도가 1부터 n(1 ≤ n ≤ 2e5)까지 총 n명의 사람이 있습니다. 이 중 1부터 k의 온도인 앞 k명이 싸움을 벌여 한명이 남을때까지 싸우려고 합니다. 각 싸움터는 숫자가 0 또는 1로 주어지는데, 0일 때에는 온도가 낮은 쪽이, 1일 때에는 온도가 높은 쪽이 승리합니다. 모든 싸움은 남아있는 사람 중 랜덤으로 두 명이 붙어 이기는 쪽은 살아남는 방식일 때, 마지막에 남아 있을 수 있는 사람의 수를 k = 1일때부터 n일때까지 순서대로 출력하세요.

이 문제의 핵심은 남아있는 사람 중 랜덤으로 두 명이 붙는다는 것이다. 다시 말하면 운만 좋으면 마지막 1:1 전까지 단 한번도 싸우지 않아도 괜찮다. 생각을 확장해 x명이 남아있는 상황에서도, 이중 x - 1명은 전부 싸우지 않은 사람(즉, 1 ~ k까지 누구여도 상관이 없다)일 수 있고 마지막 1명만이 직전에 싸워서 이긴 사람으로 확정되어 있다. 이런식으로 접근해 보면 결국 우승자를 찾기 위해서는 마지막에 1이 얼마나 연속했느냐, 0이 얼마나 연속했느냐만이 중요해진다. 그 이유는 예를 들어 0이 3연속 나왔다면 3번째 싸움에서 이긴 사람은 반드시 마지막 4명이 남아있을 때부터 그중 가장 온도가 낮았어야만 우승할 수 있기 때문이다.

개인적으로 느끼기에 접근 난이도가 많이 높았다. 마지막 연속 횟수가 정답과 관련이 있음을 관찰하기까지 여러 상황을 가정해 봐야 했다. 어떻게 했어야 더 빠르게 접근했을지 고민 중에 있다.

D. Same Count One

n(2 ≤ n ≤ 1e5)행 m(2 ≤ m ≤ 1e5)열 0과 1만으로 이루어진 행렬이 주어집니다. (nm ≤ 1e6)
원하는 행 x, y와 열 z를 선택해, (x, z)에 있는 값과 (y, z)에 있는 값을 바꾸는 연산을 할 수 있습니다.
이 연산을 최소로 사용해 모든 행에 있는 1의 개수를 같게 하려고 할 때, 연산의 최소 횟수와 어떻게 연산을 진행해야 하는지 출력하세요.

1과 0을 바꿀때에만 개수의 변화가 일어난다. 이때 반드시 1의 개수가 더 많은 행에서는 (1, 0)의 쌍을 만들어 줄 수 있다는 점에 착안해 1이 많은 행에서 적은 행으로 잘 전달해주기만 하면 되는 그리디 문제이다.

필자는 "반드시 1의 개수가 더 많은 행에서는 (1, 0)의 쌍을 만들어 줄 수 있다" 는 것을 관찰하기까지 시간이 걸렸고 약간의 시간을 빼앗겼다.

E. Two Chess Pieces (1900)

n(2 ≤ n ≤ 2e5)개의 노드로 이루어진 트리가 주어집니다. 트리의 1번 노드에 체스말 A와 B가 있습니다. A가 반드시 지나가야 하는 칸과, B가 반드시 지나가야 하는 칸이 주어집니다. A와 B는 순서 상관 없이 자신들이 지나가야 하는 칸을 모두 지난 뒤 다시 1번 노드로 돌아오고자 하는데, 반드시 A와 B 사이의 거리는 d 이하가 되도록 움직여야만 합니다. 가능한 A와 B의 총 이동거리의 최소를 구하세요.

A가 반드시 지나가야 하는 점까지 가려면 B도 A에 맞춰서 따라가야 하는 구조이다. 생각해 보면 B는 반드시 A가 지나가야 하는 점에서 d칸 위에 있는 부모의 위치에 있으면 항상 이동거리는 최선이 된다. 이 관찰을 통해 A와 B를 완전히 분리해서 생각할 수 있다. A가 반드시 가야 하는 노드들의 d칸 위에 있는 모든 점들에 대해 B가 반드시 가야 하는 노드로 처리해주고, 마찬가지로 반대로도 반드시 가야 하는 노드를 칠해주면 A와 B는 분리된다. 이는 sparse table을 활용하면 nlgn의 시간복잡도로 처리할 수 있다.

개인적으로 굉장히 마음에 들었던 문제이다. 빠르게 풀기 위해서는 트리에 대한 이해도, 그리디, sparse table 뭐 하나 빠짐없이 요구되면서도 올바르게 사고했다면 아주 빠르게 구현할 수 있는 문제였다.

F1. Magician and Pigs (Easy Version) (2400)

다음 3개의 쿼리가 n(1 ≤ n ≤ 2e5)회 주어집니다 : 쿼리가 끝난 후 남아있는 돼지의 마릿수를 구하세요. 단, 쿼리에서 x는 반드시 2e5 이하입니다.
- 1 x : x 체력의 돼지를 하나 소환합니다.
- 2 x : 모든 돼지의 체력을 x 감소시킵니다. (0 이하가 된 모든 돼지는 죽습니다.)
- 3 : 지금까지 했던 모든 연산을 다시 반복합니다. (i번째 쿼리로 3이 주어지면, 1 ~ i-1번째 쿼리를 다시 반복합니다.)

이 문제는 쿼리 3을 어떻게 처리하냐가 핵심이다. 조금 고민해 보면 3번은 다음과 같은 연산으로 치환될 수 있다.

- 3 : 현재 남아있는 돼지들의 그룹을 S라고 하고, 지금까지 2번 쿼리로 감소된 데미지의 총합을 D라고 했을 때, S를 그대로 하나 복제합니다 : 복제한 S그룹의 모든 돼지는 D의 데미지를 받습니다.

다시 말해, D가 2e5 이상이 되면 3은 "아무것도 하지 않습니다." 와 동일한 것이 된다. 그리고 D는 3이 나올 때 마다 2배씩 증가하기 때문에 2e5까지는 3이 최대 18번까지만 제대로 작동함을 알 수 있다. 이를 통해 18번의 3에 대해 각각에서 복제가 되어 D만큼 데미지를 받았는지, 안 받았는지에 따라 관리를 잘해 2^18개의 상태에 대해 계산을 잘 해 주면 남아있는 돼지의 마릿수를 O(NlgX + XlgX)에 구할 수 있다.

F2. Magician and Pigs (Hard Version) (2700)

다음 3개의 쿼리가 n(1 ≤ n ≤ 8e5)회 주어집니다 : 쿼리가 끝난 후 남아있는 돼지의 마릿수를 구하세요. 단, 쿼리에서 x는 반드시 1e9 이하입니다.
- 1 x : x 체력의 돼지를 하나 소환합니다.
- 2 x : 모든 돼지의 체력을 x 감소시킵니다. (0 이하가 된 모든 돼지는 죽습니다.)
- 3 : 지금까지 했던 모든 연산을 다시 반복합니다. (i번째 쿼리로 3이 주어지면, 1 ~ i-1번째 쿼리를 다시 반복합니다.)

F1의 접근으로는 X를 때내기가 어렵다. X항을 시간복잡도에서 때내기 위해서는 관점을 바꾸어 1 쿼리로 생성된 돼지 각각을 기준으로 보아야 한다. 돼지 각각을 기준으로 쿼리 2는 돼지의 체력을 x 감소시키는 쿼리, 쿼리 3은 돼지를 체력 y 감소시킨 상태로 복사시키는 쿼리로 이루어져 있다. 따라서 앞선 F1의 설명과 같은 원리로 앞선 lgX개의 쿼리 3만을 따지면 각각의 돼지가 총 몇회 복사됐는지를 계산할 수 있다. 문제는 이걸 계산하는 방법은 위와 완전히 동일하다는 점인데, 돼지 각각을 기준으로 생각했을 때에는 추가적으로 다음과 같은 관찰을 이용할 수 있다.

관찰 : 모든 쿼리 3의 y를 순서대로 나열했을 때, 임의의 y_i는 항상 1~i-1까지의 ∑y보다 크다. 증명은 생략하겠다. (공비가 2인 등비수열의 총합을 생각하면 쉽다) 이를 통해 가장 뒷쪽의 y_i부터 다음과 같은 판단을 할 수 있다.

- 현재 돼지의 체력 H가 y_i보다 큰 경우 : y_i만큼 깎고 재귀적으로 이어나간다. + y_i를 깎지 않는다. (이 경우 그 앞의 숫자들을 모두 더해도 체력이 0보다 큼은 자명하다. 따라서 경우의수를 2^i로 나타낼 수 있다.)

- 현재 돼지의 체력 H가 y_i보다 작은 경우 : y_i만큼 깎을 수는 없다, 깎지 않고 재귀적으로 이어나간다.

다음과 같은 이유로 모든 돼지에 대해 lgX회의 연산으로 복사된 횟수를 계산할 수 있으며 이 방법대로 돼지의 마릿수를 O(NlgX)에 구할 수 있다.