알고리즘/온라인 대회

Codeforces Good Bye 2020 후기

kdh9949 2021. 1. 7. 01:51

지난 12월 30일에 열린 Codeforces Good Bye 2020 대회에 참여하였다. 대회 링크

결과는 30등으로, 레이팅은 무려 110이나 올라서 2763이 되었다. kriii님과 사이좋게 붙어있는 모습을 볼 수 있다. 다음 라운드에서 잘 하면 2800도 넘길 수 있을 것 같다.

이 라운드 도중에 무슨 Telegram 서버에서 대규모로 A~F 솔루션이 공유되는 사건이 있었다고 한다. 이런 데서 치팅하는 사람들은 (BOJ에서 solved.ac 랭킹 올리려고 치팅하는 사람들도..) 그런 짓이 순도 100%의 시간낭비라는 것을 좀 깨달았으면 좋겠다.

 

A(1min) : \( (0, 1) \) 에 점이 하나 있고, x축 상에 점이 N개 있다. (N 50) 각 점의 좌표는 \( (x_i, 0) \) 으로 주어진다. 이들 점 중 3개를 골라 넓이가 양수인 삼각형을 만든다고 할 때, 몇 가지 넓이가 가능한지 출력하라.

더보기

\( (0,1) \)은 무조건 골라야 한다. 그러면 밑변의 길이가 삼각형의 넓이를 결정하므로, x축 위에서 고른 두 점의 x좌표 차이로 가능한 값이 몇 개인지 세면 된다. 그냥 다 set에 때려박고 size를 출력하면 된다.

 

B(4min) : N개의 자연수가 비내림차순(감소하지 않는 순서)으로 정렬되어 주어진다 (N ≤ 100,000). 각 자연수에 1을 더할지 말지를 각각 선택할 수 있다고 할 때, 서로 다른 수의 개수를 최대화하여라.

더보기

cnt[i]를 i의 개수라 하자. i를 1부터 증가시키면서, cnt[i]가 2 이상일 경우 cnt[i+1]을 하나 늘려주면 된다. (즉, i 하나를 i+1로 바꾸면 된다.)

다른 방법으로는, 주어진 배열을 앞에서부터 보면서 "a[i-1] >= a[i]일 때 a[i]를 1 증가"하는 것을 반복해도 된다.

 

C(16min) : 길이 100,000 이하의 문자열이 주어진다. 문자열에서 길이 1 초과의 회문(palindrome)이 나타나지 않도록 한다고 할 때, 최소 몇 글자를 수정해야 하는지 구하여라.

더보기

길이가 1 초과인 팰린드롬은 정가운데에 길이가 2 또는 3인 팰린드롬을 항상 포함하므로, 길이가 2인 팰린드롬과 3인 팰린드롬만 신경써주면 됨을 일단 알 수 있다.

이제 Greedy 알고리즘을 적용하는데, 문자열을 앞에서부터 훑으면서 i번째 글자가 (i-1)번째 또는 (i-2)번째 글자와 같은 순간이 오면 i번째 글자를 다른 것으로 바꾸는 것을 반복한다. i번째 글자를 다른 것으로 바꿀 때에는 그 앞뒤로 2글자 범위 내에 있는 것과 안 겹치는 것으로 고르면 충분하다. 나는 그런 글자를 골라주는 함수를 따로 짰는데, 지금 생각해 보니까 최소 횟수만 구하면 되기 때문에 그냥 "$"같이 아예 이상한 글자로 바꿔줘도 똑같다.

처음에는 Greedy에 대한 확신이 없어서 D를 먼저 풀고 돌아와서 C를 풀었다.


D(10min) : 정점이 N개인 트리가 주어진다 (N ≤ 100,000). 각 정점에는 가중치가 있다. N-1개의 간선들에 색을 칠할 것인데, 같은 색으로 칠해진 간선들에 대해 그 색의 가치는 "해당 색의 간선들과 인접해 있는 정점들로 이루어진 연결 성분들 중, 가장 정점 가중치의 합이 큰 연결 성분의 가중치 합"으로 정의된다. 색을 1종류, 2종류, ..., (N-1)종류 쓸 수 있는 경우 각각에 대해 모든 색에 대한 가치 합의 최댓값을 출력하라.

더보기

문제가 좀 읽기 싫게 생겼는데, 적당히 스킵하고 예제를 읽으면서 관찰을 몇 개 하면 다음과 같다.
- 색을 1종류 쓸 때는 답이 각 정점의 가중치의 합이다.
- 색을 N-1종류 쓸 때는 답이 각 정점의 (가중치 * degree)의 합이다.
- 답이 증가하는 속도가 점차 감소한다. 즉, i종류 -> (i+1)종류로 갈 때 답이 X만큼 늘어났다고 하면 (i+1)종류 -> (i+2)종류로 갈 때는 답이 X 이하로 늘어난다.

예제를 읽으면서 좀 더 생각을 해 보면 가중치가 큰 정점부터 그 정점이 답에 기여하는 계수를 1 -> 2 -> ... -> (그 정점의 degree)까지 Greedy하게 늘려가는 방식이 최적이라고 짐작을 할 수 있고, 그걸 짜서 내면 맞는다.

"같은 색깔의 간선들은 하나의 컴포넌트를 이루는 것이 최적이다" 등의 관찰로부터 위의 짐작이 실제로 맞다는 것을 생각해 낼 수도 있긴 하지만, 그걸 하는 데 드는 노력에 비해 그냥 예제 대충 보고 때려맞히는 게 너무 쉬운 것 같다. 좀 아쉬운 부분. B, C, D가 모두 대충 짠 그리디로 풀린다는 점도 좀 아쉽다.

 

E(24min) : 길이 N의 수열 \( x_i \) 가 주어진다 (N ≤ 500,000, \( x_i < 2^{60} \)). 다음 값을 10억 7로 나눈 나머지를 구하여라 : \( \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=1}^{N} (x_i \& x_j) \cdot (x_j | x_k) \)

더보기

문제에서 성의없음이 잔뜩 느껴진다.. 아무튼 시그마를 적당히 풀어보면 \( \sum_{j=1}^{N} ( \sum_{i=1}^{N} x_j \& x_i ) \cdot ( \sum_{k=1}^{N} x_j | x_k ) \) 의 값을 구하면 됨을 일단 알 수 있다.

이제 각 \( j \) 에 대해 \( \sum_{i=1}^{N} x_j \& x_i \) 와 \( \sum_{k=1}^{N} x_j | x_k \)의 값을 빠르게 구해야 하는데 이것은 비트별로 쪼개서 접근하면 된다. cnt[i]를 i번째 비트가 1인 수의 개수라고 하면, and와 or 각각에 대해서 \( x_j \)의 i번째 비트가 1인지 0인지에 따라 해당 비트에서 1이 몇 번 더해지는지를 알 수 있다. and의 경우 i번째 비트가 1일 경우에만 cnt[i]만큼이 더해지고, or의 경우 i번째 비트가 1일 경우 N만큼, 0일 경우 cnt[i]만큼이 더해진다. 이것을 모든 비트에 대해 계산해 주면 총합을 \( j \) 하나당 60번의 연산으로 구할 수 있다.

 

F(48min) : 벡터 덧셈이 bitwise XOR로 정의된 \( \{0,1\}^M \) 벡터공간(일명 XOR basis) 상에서 벡터 N개가 주어진다 (N, M ≤ 500,000). 그런데, 각 벡터는 최대 2개의 원소만 1이고 나머지는 0이다. 이 때, N개의 벡터들이 이루는 부분공간을 span하는 최소 크기의 부분집합을 고르고, 그 때 그 부분공간에 몇 개의 벡터가 있는지를 구하라 (mod 10억 7). 최소 크기 부분집합이 여러 개 있을 경우에는 벡터를 입력에서 주어진 순서대로 번호를 매겼을 때 그 번호의 수열이 사전순으로 가장 앞에 오는 것을 구하여라.

더보기

"아 모르면 풀지 마 ㅋㅋ" 라고 써 있는 듯한 문제다.. F에 이런 걸 굳이 냈어야 하나 싶다. 심지어 치팅까지 터져서 라운드가 좀 망했다고 볼 수 있다.

아무튼 이런 XOR basis 가지고 노는 문제를 좀 풀어 봤다면 그냥 주어진 벡터들의 기저(basis)를 구하는 문제임을 알 수 있다. 입력에 걸린 이상한 조건을 봤을 때, Gaussian Elimination을 그 조건으로 어떻게 최적화하면 풀 수 있겠다는 게 매우 뻔하게 보인다. Gaussian Elimination을 Basis에 하나씩 추가하는 식으로 구현하면 사전순 최소 어쩌구 조건도 매우 간단하게 고려할 수 있다.

지금까지 구한 Basis에 벡터가 하나 새로 들어오는 과정을 생각해 보자. 1이 2개짜리인 벡터들만 우선 고려한다고 하면, 아래 그림처럼 간선을 타고 가는 것으로 추가하는 과정을 표현할 수 있다.

새로 들어오는 벡터에 1이 1개라면 그 1이 간선을 타고 가다가 더 갈 곳이 없는 시점에서 멈추게 된다. 1이 2개여도 각 1이 독립적으로 간선을 타고 간다고 생각하면 됨을 알 수 있다. (순서는 중요하지 않다) 만약 1 2개가 같은 지점에서 멈추게 되면 그 시점에서 둘이 더해져서 0이 되기 때문에 basis에 새로 추가가 일어나지 않는다.

이제 1이 1개짜리인 벡터를 고려하는 것은 그냥 해당하는 자리에 있으면 빼 주는 것이므로 간단하다. 마지막에 남는 1이 있다면 새로 간선을 추가하거나(1이 2개), 그냥 해당 위치에 체크를 해 주면(1이 1개) 된다.

그런데 간선을 일일이 타고 가게 되면 최악의 경우 벡터 하나를 추가할 때마다 \( O(N) \) 이 걸리게 되므로 간선을 빠르게 타야 한다. 간선들의 모양새가 rooted tree 여러 개로 나타난다는 것을 관찰하면 (각 정점의 outdegree가 1을 초과할 수 없기 때문이다) union-find 자료구조로 이것을 최적화할 수 있다. 그냥 a->b 간선이 추가될 때 a가 속한 집합의 부모를 b가 속한 집합으로 해주면 된다.

부분공간에 몇 개의 벡터가 있는지는 (예제로 짐작 가능하듯이) 기저의 dimension이 d일 때 \( 2^d \) 으로 구할 수 있다.

풀면서 2번인가 틀렸는데, 배열 크기를 잘못 적어서였다. 이거 안 틀렸으면 한 20등 정도 했을 거 같은데 좀 아쉽다..

 

G(87min) : 두 문자열 \( s_0 \)와 \( t \)가 주어진다(\( |s_0| \le 100, |t| \le 100,000 \)). \( t \) 의 길이를 N이라고 하면, \( s_i (1 \le i \le N) \)는 \( s_{i-1} \), (\( t \)의 \( i \)번째 글자), \( s_{i-1} \)을 순서대로 붙인 것으로 정의된다.

쿼리가 총 Q개 주어지는데(Q ≤ 100,000), 각 쿼리마다 정수 k와(0 ≤ k ≤ N) 문자열이 주어지면 해당 문자열이 \( s_k \)에서 연속한 부분문자열로 몇 번 등장하는지를 mod 10억7로 출력해야 한다. (모든 쿼리에서 문자열 길이 합 1,000,000)

더보기

쿼리에서 주어진 문자열에 대해, 그 문자열을 완전히 포함하는 (길이가 같거나 더 큰) 가장 작은 \( s_i \)를 \( s_c \)라 하자. 이제 \( s_k \)는 \( s_c \)가 \( 2^{k-c} \)번 나타나고 그 사이에 \( t \)에서 뽑은 글자들이 한 글자씩 껴 있는 꼴로 생각할 수 있다. 이제 등장 횟수를 "어떤 \( s_c \)안에 완전히 포함되어 등장하는 것"과 "두 개의 \( s_c \) 사이에 걸쳐서 등장하는 것"으로 나누어서 세 보자.

첫 번째 경우는 그냥 \( s_c \)를 구한 다음에 KMP나 해싱 등으로 적당히 빨리 등장 횟수를 세어서 \( 2^{k-c} \)를 곱하면 끝이다.

두 번째 경우를 빠르게 세기 위한 핵심 관찰은 두 개의 \( s_c \) 사이에 끼어 있는 문자는 항상 한 글자라는 것이다. 그러므로, 그 사이에 낀 한 글자가 'a'인 경우부터 'z'인 경우까지 총 26가지 경우 각각에 대해 (그 글자가 나타나는 횟수) * (그 때 쿼리 문자열의 등장 횟수)를 다 구해서 더해주면 된다.

각 알파벳에 대해 "\( s_i \)에 나타나는 \( t \)의 글자들 중 해당 알파벳이 몇 개 있는가"를 미리 전처리해 놓으면, \( s_k \)에서 \( s_c \)에 포함되는 부분을 제외하고 나머지 부분, 즉 사이에 낀 글자들 중 각 알파벳이 몇 번 나타나는지를 바로 알 수 있다. 각 알파벳에 대해 그 알파벳을 사이에 낀 상태에서 쿼리 문자열의 등장 횟수는 \( s_c \) + (해당 알파벳) + \( s_c \) 라는 문자열에서 가운데 낀 알파벳을 중심으로 양 옆 (쿼리 문자열 길이 - 1)개의 문자만 남긴 부분문자열을 하나 만들고, 첫 번째 경우를 셀 때처럼 똑같이 세 주면 된다.

 

H : 문제가 너무 복잡해서 안 읽었다..

 

I : 재밌고 매우 어려워 보이는 Interactive 문제이다. 이상한 걸 몇 번 시도하다가 어림도 없다는 것을 깨닫고 접었다.

'알고리즘 > 온라인 대회' 카테고리의 다른 글

2020 ICPC Asia Macau Regional Contest  (0) 2021.08.21
Codeforces Round #736  (0) 2021.08.20
Codeforces Round #691, #692 후기  (0) 2020.12.21
NERC 2020 Virtual Participation  (0) 2020.12.19
Topcoder SRM 794, 795 후기  (0) 2020.12.16