plast / 코딩공부

SUAPC 2등!!

사실 팀 목표는 1등이였고, 가능성도 꽤 높았다고 생각했는데 이런저런 아쉽게 됐다. 이 셋 기준으로는 아무리 잘했어도 10솔 하기는 힘들었을 것 같다. 1등팀이 굉장히 잘했다. ㄷㄷ

피드백 할만 한 문제들만 몇개 정리한다.

C. 점수 내기

A와 B가 게임을 합니다. A는 조건을 만족하는 최대 점수 문자열을, B는 조건을 만족하는 최소 점수 문자열을 만들려고 합니다. 다음 조건에서 A와 B가 최선을 다했을 때 받을 수 있는 점수를 출력해주세요. (A와 B가 만드는 문자열은 알파벳 소문자와 숫자를 이용할 수 있습니다.)
조건 : 만든 문자열 S에 대해, '접두사 목록'에 존재하는 문자열 S의 접두사들의 점수를 모두 더합니다. '접미사 목록'에 존재하는 문자열S의 접미사들의 점수를 모두 더합니다.
총 q(3e5)개의 쿼리에 대해, 다음 4 종류의 쿼리가 주어집니다. 주어지는 쿼리의 문자열 길이의 총합은 1e6을 넘지 않습니다.
쿼리 1 : 접두사 목록에 문자열 T와 점수 x를 추가합니다. (T는 알파벳 소문자만으로 이루어져 있습니다.)
쿼리 2 : 접미사 목록에 문자열 T와 점수 x를 추가합니다. (T는 알파벳 소문자만으로 이루어져 있습니다.)
쿼리 3 : A가 만들수 있는 최대 점수를 출력합니다.
쿼리 4 : B가 만들수 있는 최소 점수를 출력합니다.

풀이는 다음과 같다.

1. 접두사 목록과 접미사 목록을 분리해서 생각할 수 있다. 예를 들어 접두사 목록 abc와 접미사 목록 ba를 쓴다고 할 때, 반드시 abc0ba와 같이 가운데에 숫자로 벽을 칠 경우 모든 예외를 막을 수 있다.

2. 접두사 목록에서 최대 점수/최소 점수 접두사를 판단하기 위해 트라이 + lazy로 관리할 수 있다. 자세한 관리방법은 다음과 같다.

2 - a. 트라이에 꼭 필요한 정보 : max, min, num, lazy

2 - a. 트라이에 새로운 노드가 입력된다. -> 그냥 큰 문제 없이 이전 노드의 num을 가져와 갱신해주면 된다.

2 - b. 트라이에 기존의 노드가 입력된다. -> max, min, num에 모두 x만큼 갱신한다. lazy를 이용해 자신의 아랫 노드에 전부 뿌려주며, 동시에 자신의 parent들의 max, min을 갱신한다.

10틀... 10틀.......

이 문제에 한이 엄청 쌓였다....

풀이는 거의 바로 찾았지만, 트라이도 처음 써봤고 거기에 익숙치 않은 lazy비빔밥이 얹혀지면서 제대로 폭망했다. 처음 코드에서 고칠게 이중 삼중 사중으로 있었다.(...) 마지막까지 틀렸지만 사실 마지막에 제출한 코드에서 한 줄만 고쳤다면 정답코드였다. 그것은 바로 lazy를 갱신해줄때 lazy값을 0으로 비워주는것... 실화냐..

디버깅에 대해서도 고민을 많이 하게 됐다. 예전에는 반례를 무지성으로 찾아내면서 디버깅하는것을 선호했는데, 그냥 코드를 열심히 읽는 편이 훨 나을 것 같다. 코드 읽는 실력도 예전보다 훨씬훨씬 늘었고 걍 코드만 3번 읽었으면 오류를 다 찾았을 것 같다. 2시간동안 뭘 한건지 모르겠다..

E. 슬라이딩 퍼즐 마스터

N * M (N * M ≤ 9) 보드판이 있습니다. 여기에는 1 ~ (N * M - 1)까지의 숫자와, 빈 칸 하나가 주어집니다. 다음 두 가지 연산중 하나만을 이용해, 모든 상태를 중복 없이 전부 나타내세요.
연산 1) 빈 칸에 인접한 숫자를 이동시킵니다.
연산 2) 인접한 숫자 두개를 서로 바꿔치기합니다.

풀이는 다음과 같다.

1. 사실 빈 칸은 숫자와 동일시 해도 상관 없다.

2. 2차원 배열처럼 보이지만, 사실 스네이크 형식으로 본다면 1차원 배열과 똑같다. 즉, 1차원 배열 9개의 9! 상태를 바로 인접한 숫자와 swap해서 모든 상태를 한번씩 이동하는 문제가 된다.

3. 길이가 n인 순열을 관찰해보면, 가장 앞 숫자 a를 골라 a를 가장 오른쪽으로 보내보자. 그러면 a를 제외한 (n - 1)길이의 순열에 대해 길이가 n인 순열에서 나올 수 있는 모든 상황이 기록된다. 이를 바탕으로 a를 계속 좌우 끝과 끝으로 이동시켜 가며 (n - 1)길이의 순열에 대해 재귀적으로 반복하는 방식으로 풀 수 있다. (Steinhaus–Johnson–Trotter Algorithm)

이 문제는 다음 두 가지 이유로 난이도가 굉장히 높다.

1) 풀이 2, 3번의 관찰이 어렵다. (특히 3번)

2) 풀이 3번에 해당하는 재귀함수가 구현이 상당히 까다롭다. (본인은 역순으로 구현을 했는데, 정답자 코드를 읽어보니 vector<int>를 인자로 받아 n = 9에서 재귀로 구현하던데 그 편이 한참은 쉬울 것 같다..)

이 문제는 돌아가도 풀기 어려웠을 것 같다. 풀이 2 관찰까지는 금방 했던 편이였는데, 풀이 3 관찰은 아무리 생각해봐도 난이도가 너무 너무 높다.. 이 문제는 구현 난이도도 상당하다.

이런 유형의 문제를 풀기 위해서는 순열의 특징에 관해 깊게 공부해봐야 할 것 같다. 최근 AGC 61 A에서도 비슷한 문제가 나와 크게 데였다. 그 문제는 짝수 길이의 순열에서만 생기는 인접한 원소끼리의 특징을 바탕으로 했다. 이 문제는 원소를 하나 쭉 돌아갈 때 나머지 순열의 위치를 관찰하라는데.. 솔직히 발상 난이도가 지나칠 정도로 높다. 어떻게 발상하는건지 아직도 이해가 안간다.

I. UFO in Sinchon

N(1e9) * M(1e9) 짜리 격자에서 K(2e5)명의 사람이 있고 Q(2e5)번 순서대로 UFO가 나타납니다.
K명의 사람은 UFO가 나타날 때마다 매 턴 택시거리로 가장 가까워지도록 가로, 세로, 대각선 8방향 중 한 방향으로 이동합니다. UFO와 같은 위치에 있다면 이동하지 않습니다.
UFO는 (x, y, t) 형태로 나타나며 (x, y)위치에 나타나 t(1e9)턴 후 사라집니다.
K명의 최종 위치를 모두 구해주세요.

풀이는 다음과 같다.

1. x와 y는 분리해서 생각해도 된다. 즉, 1차원에서 현재 위치가 a, 우주선이 (x, t)형태로 주어질 때 q번의 ufo가 나타나고 갈 위치를 잘 관리하는 문제로 변한다.

2. 우주선이 (x, t)로 나타나면, (x - t)보다 작은 경우 a + t, (x - t ~ x + t)의 경우 x, (x + t)보다 큰 경우 a - t의 위치로 최종 이동한다.

3. 이 정보를 바탕으로 lazy segment tree에 y = ax + b(순서대로 (a = 1, b = t), (a = 0, b = x), (a = 1, b = -t))를 잘 관리해 갱신한다.

이건 접근 1은 내가 했지만 2, 3번은 다른 팀원이 했다. 사실 2~3은 처음 보는 유형이였어서 시간을 들였어도 쉽게 풀지는 못했을 것 같다.

추가 예정

L. 따로 걸어가기

N(2e5)행 M(2e5)열의 2차원 격자가 있습니다. 두 행인 A, B에 대해, 다음 경우의 수를 구하세요.
- A, B가 1행 1열에서 N행 M열까지 오른쪽, 혹은 아랫쪽 방향으로 한칸씩으로만 이동해 도착할 때, 둘이 시작점과 끝점을 제외한 모든 점에서 마주치지 않는 가짓수 

풀이는 다음과 같다.

1. 두명의 이동은 결국 오른쪽과 아래중 하나의 경로를 동시에 택하는 선택과정의 연속이라고 볼 수 있다. (두 명의 경로를 따로 보지 않고, 두명이 동시에 이동한다고 보자.)

2. 이동방식은 4가지밖에 없고, 특징을 잘 살펴보면 그 안에서도 규칙이 발생한다. 규칙은 다음과 같다.

2 - 1. 이동 방식은 (D, D), (D, R), (R, D), (R, R) 밖에 없다. ( (R, D)는 1번 사람이 오른쪽으로, 2번 사람이 아래로 이동한다는 뜻이다.) 이 이동방식을 순서대로 이동1, 이동2, 이동3, 이동4라고 하자.

2 - 2. 1, 2번 사람은 둘 다 D를 총 n번, R을 총 m번씩 이동해야 하기 때문에 이동횟수 간의 연립식이 생긴다. 정리하면 이동1이 k회 이동했을 때, 이동2 = 이동3 = n - k번, 이동4 = m - n + k번 이동하게 된다.

2 - 3. 일반성을 잃지 않고 n ≥ m이며 1번 사람은 처음에 D로, 2번 사람은 처음에 R로 이동했다고 치자. (n < m인 경우에는 n, m을 바꿔주면 되고, 1번 사람과 2번 사람이 반대로 이동한 경우는 정확히 횟수가 똑같기 때문에 최종 답에서 2배 해주면 된다.) 그러면 항상 이동2 횟수 ≥ 이동3 횟수를 유지해야 하기 때문에 (이동2, 이동3)은 올바른 괄호쌍을 만드는 카탈란 수로 표현해줄 수 있다.

2 - 4. 1번 이동 각 가능한 k에 대해, 전체 이동에서 이동1의 위치, 이동4의 위치, (이동 2 + 이동 3)의 위치를 선정하는 가짓수 * 이동2와 이동3을 적절히 배치하는 카탈란수 가짓수를 정리하면 O(n)에 총 가짓수가 나온다.

나는 대회때 한 10분정도 보고 포기한 문제인데, 나중에 풀어보고 난 후 난이도는 생각했던 것보다는 쉬웠다. 접근 1이 생소한 것 같고, 접근 1을 올바르게 했다면 뒷부분은 대회때 풀었을 것 같다.

접근 1은 완전히 처음 보는 유형인데, '두 명이 서로 다르게 이동한 경로' 라는 키워드에서 생각해볼 수 있을법한 좋은 접근인 것 같다. 항상 총 가짓수 구하는 유형에 약하다. 이쪽 유형도 많이 공부해야겠다는 생각이 자주 든다.

다음 편 보기

나눗셈 정리
a는 정수, b는 자연수라고 하자. 이 때, a = bq + r (0 ≤ r < b) 를 만족하는 정수 q와 r은 유일하게 존재한다.
이 때, q를 '몫', r을 '나머지' 라고 하며 r = 0인 경우를 특히 'a가 b에 나누어떨어진다' 라고 표현한다.

나눗셈 정리는 정수론의 기본식 중 하나인데, 이 식에서 특히 많은 관심을 가지는 부분은 나머지인 r이다. 정수론에서는 나머지에 관심이 많다. 나머지는 무수히 많은 정수를 유한개로 분류해주기 때문이다. 간단한 예를 들어보자.

제곱수를 3으로 나눈 나머지가 2이다. 그 수는 무엇일까?

한번 10까지 제곱해서 값을 구해보자. 1의 제곱인 1은? 3으로 나눈 나머지가 1이다. 마찬가지로 4, 9, 16, 25, 36, ... 이 값들은 어떨까? 이상하게도 3으로 나눈 나머지가 0 또는 1이다. 2인 경우는 없다.

실제로 어떤 제곱수도 3으로 나눈 나머지는 2일 수 없다. 모든 자연수는 3으로 나눈 나머지가 0, 1, 2중 하나인데, 각각의 제곱수는 3으로 나눈 나머지가 0, 1, 1이 되기 때문이다.

숫자는 무한하다. 하지만 그 무수히 많은 숫자들도 3으로 나눈 나머지는 '0', '1', '2' 총 3개 중 하나이다. 이 덕분에 3종류의 숫자만 본다면 무수히 많은 제곱수중 3으로 나눈 나머지가 2인 수는 없다는 것을 쉽게 증명할 수 있다.

수많은 정수를 유한개로 분류했을 때 나오는 여러 특징들을 바탕으로 다양한 문제를 풀어낼 수 있으며 이 기반은 나눗셈 정리가 바탕이 된다.

1) 홀짝성

나머지의 분류를 활용하는 가장 대표적인 방식은 홀수와 짝수이다. 모든 정수는 홀수와 짝수 2가지로 분류된다. 홀수와 짝수라는 개념은 초등학생 때부터 배우며 이미 많이 풀어봤겠지만, 홀수와 짝수의 특징을 이용한 문제들은 수없이 많고 난이도도 상당하다. 앞으로 그러한 문제들을 많이 볼 것이기 때문에 충분히 익히고 넘어가자.

홀수와 짝수의 특징
- 짝수 ± 짝수, 홀수 ± 홀수는 반드시 짝수이다.
- 짝수 ± 홀수, 홀수 ± 짝수는 반드시 홀수이다.
- 짝수 × 홀수, 짝수 × 짝수는 반드시 짝수이다.
- 홀수 × 홀수는 반드시 홀수이다.

예제 1.1 (난이도 ☆) : 축구팀 5팀이 아무렇게나 시합을 했을 때, 모든 팀이 홀수번 시합을 할 수 있는지 판단하세요.

예제 1.2 (난이도 ☆) : 0과 1만으로 이루어진 수열이 있습니다. 모든 숫자 사이에 +혹은 -를 넣어서 식을 만들려고 하는데, 이 식의 절댓값이 최소가 되도록 하고 싶습니다. 주어진 수열에서 최솟값을 구하세요.

a) 0 1 1 0 1

b) 1 1 0 1 1

c) 일반적인 모든 수열

- Codeforces Polynomial Round 2022 A 각색

특히 코드포스에서는 홀짝성을 이용하는 문제가 굉장히 많다. 이번에는 A번의 문제로 가지고 왔지만 이 문제는 홀짝성만 관찰해도 문제를 풀 수 있어서 그렇고, 난이도가 높은 문제에서도 기본 중의 기본으로 활용되는 경우가 널렸다. 예제 1.2는 홀짝성의 일반화된 버전이기도 하므로 충분히 이해가 되지 않았다면 몇번이고 곱씹고 넘어가는 것이 좋다. 

연습문제 (가능하면 난이도 순으로 배열했습니다.) 

백준 21312 : 홀짝 칵테일

Codeforces Round 838 A

Codeforces Deltix Round, Autumn 2021 A

Codeforces Hello 2023 F

Atcoder Regular Contest 155 D

2) 나머지의 성질 일반화

홀짝성은 나머지의 성질 중 특별한 경우이다. 2로 나눈 나머지에 대해서 설명할때 홀짝성이라는 단어를 붙이곤 한다. 하지만 언뜻 보면 홀짝성에서만 쓰일 것 같더라도 어느 숫자로 나눈 나머지에서든 동일한 성질이 보일 수 있다.

특히 비둘기집을 활용하는 경우가 흔하다

예제 1.3 (난이도 ☆) : 서로 다른 자연수가 5개가 있을 때, 항상 두 수의 차이가 4의 배수가 되도록 두 개의 숫자를 고를 수 있음을 보이시오.

예제 1.4 (난이도 ★☆) : 자연수로 이루어진 수열 a가 있습니다. 수열 a의 모든 원소에 대해서 다음을 만족하는 자연수 x가 있는지 알아보고 싶습니다: 주어진 수열에서 그러한 x가 있는지 없는지 판단하세요.
- 수열 a의 아무 자연수 a[i], a[j] 두개를 골랐을 때, 항상 gcd(a[i] + x, a[j] + x) = 1을 만족한다.

a) 2 4 8

b) 2 3 4 5

c) 3 5 7 9 11 13

d) 일반적인 모든 수열

- Codeforces Good Bye 2022 C 각색

위에 문제들을 풀어보면, 홀짝성에서만 적용될 것 처럼 보이던 특징들이 고민해보면 일반화되는 경우가 상당히 많다. 홀짝성이 문제의 접근에서 중요한 것으로 보일 때에는 한번 쯤 이런 생각도 해보자. '정말 2로 나눴을때만 생기는 특징이야?'

연습문제

백준 2839 : 설탕 배달

3) 합동

합동은 정수론에서 굉장히 중요한 요소이다. 우선 간단한 문제를 하나 풀어보자.

2의 99999999999제곱을 3으로 나눈 나머지는 몇일까?

이 문제의 답은 무엇일까? 직접 하나씩 제곱을 해보면 특징이 보인다. 2의 1제곱은 3으로 나눈 나머지가 2, 2제곱은 1, 3제곱은 2, 4제곱은 1, ...

2의 홀수제곱은 3으로 나눈 나머지가 2이고, 2의 짝수제곱은 3으로 나눈 나머지가 1이다. 따라서 위 문제의 답은 2일 것이라고 추론해볼 수 있다. (수학적 귀납법 등을 이용하면 증명도 가능하다.)

이 문제는 쉽게 풀었다. 왜냐하면 특징이 너무 뚜렷했다. 그렇다면 3의 99999999999제곱을 100으로 나눈 나머지는 어떻게 구할까? 그 때도 비슷한 방식으로 풀 수 있을까?.. 쉽지 않을 것이다.

이런 다양한 식에서 숫자의 나머지를 어떻게 빠르게 구할 수 있을지의 고민 중에 도입된 개념이 바로 합동이라는 개념이다.

정수론에서는 중요도가 매우 높고 나머지를 구하기 위해 특히 중요하지만, ps에서는 컴퓨터를 활용하기 때문에 페르마의 소정리, 오일러 정리, 중국인의 나머지 정리 등등 나머지를 빠르게 구하는 기술들은 ps에서는 엄청나게 중요한 분야는 아니다. ps에서는 정수론의 지식 대신 알고리즘을 활용해 어렵지 않게 나머지를 구할 수 있다. ps에서 나머지를 구하라는 대부분의 문제들은 순전히 구하려는 숫자가 long long int (2^63)를 넘어가서 그런 경우가 많다. 따라서 합동식의 개념만 충분히 이해하고 넘어가자.

예제 1.5 : 추가예정

예제 1.6 (난이도 ★) : i = 1 ~ n에 대해 ∑i^2 의 값에 2022를 곱한 값을 (1e9 + 7)로 나눈 나머지를 구하고자 합니다. 이 값을 구하는데 long long (8e18) 범위를 초과할 수 없으며 총 1억회 이상의 덧셈, 뺄셈, 곱셈, 나머지 연산을 할 수 없습니다. 다음 n에서 어떻게 연산하는 것이 좋을지 판단하세요.

a) n ≤ 1e5

b) n ≤ 1e9

- Codeforces Round #841 B 각색

합동식의 나눗셈은 특정 상황에서만 만족한다는 점을 주의하자. 물론 나중에 나올 잉여역수를 이용하면 나눗셈도 할 수 있다. 이에 대한 내용은 페르마 소정리 파트때 설명하겠다.

연습문제

추가 예정

댓글로 질문, 피드백 언제나 환영합니다 :)

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로 만들수 있는 수열의 개수를 구하세요. 

추가예정 

"이것만 공부하면 PS할때 수학 더 안봐도 된다!!!"

를 목표로 만든 페이지이다.

다음과 같은 원칙을 바탕으로 글을 쓸 예정이다:

• 누가 읽더라도 이해할 수 있도록 최대한 간결하게 전달한다.
• 백준 플래티넘1 이하 문제 / 코드포스 2400 이하 문제에서 필요한 수학을 최대한 전부 커버한다.
• 정수론 서적, 올림피아드 문제 등을 바탕으로 충분한 자료조사를 한 뒤 글을 작성한다.

목차

1. 나머지와 합동
2. 유클리드 호제법 : 최대공약수
3. 에라토스테네스의 체 : 소수와 소인수분해
4. 팩토리얼과 이항계수
5. 비트연산자
6. 포함배제의 원리 (심화)
7. 페르마의 소정리 (심화)

댓글로 질문, 피드백 언제나 환영합니다 :)

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)에 구할 수 있다.