Codeforces Round #833 (Div. 2)

A. The Ultimate Square

code

문제 설명

총 \(N\)개의 직사각형이 있다. \(i\)번째 직사각형은 세로의 길이가 1이고, 가로의 길이가 \([\frac{N}{2}]\)이다. \(N\)개의 직사각형을 회전시키지 않고 만들 수 있는 가장 큰 정사각형의 한 변의 크기를 출력해야 한다.

알고리즘

먼저 \(2N\)개의 직사각형이 있다고 하자. 이 \(2N\)개의 직사각형을 서로 다른 \(N\)개 직사각형 묶음으로 쪼개자. 그렇다면 각 묶음은 \(1 \times 1\) 크기의 직사각형부터 \(1 \times N\) 크기의 직사각형까지 총 \(N\)개의 서로 다른 모양의 직시각형이 있다. 이 \(N\)개의 직사각형을 아래와 같이 계단 모양으로 배열해보자.

\(2N\)개의 직사각형으로는 위 계단 모양을 2개 만들 수 있고, 따라서 두 계단모양을 겹쳐 \(N+1 \times N\) 모양의 직사각형을 만들 수 있다.

맨 아랫줄을 지우면 이는 한 변의 길이가 \(N\)인 정사각형이 되고, 따라서 \(2N\)개의 직사각형 또는 \(2N-1\)개의 직사각형으로 한 변의 길이가 \(N\)인 정사각형을 만들 수 있고, 이는 곧 가장 큰 정사각형이다.

따라서 \(N\)개의 직사각형으로 만들 수 있는 가장 큰 정사각형의 크기는 \([\frac{N + 1}{2}] 이다.

 

B. Diverse Substrings

code

문제 설명

숫자로만 이루어진 문자열 \(s\)는 아래 조건을 만족하면 diverse하다고 한다.

 

문자열 \(s\)에 있는 숫자가 총 \(n\)종류일 때, 문자열에 있는 각 숫자의 개수가 \(n\)개 이하여야 한다.

 

길이가 최대 10만이고 숫자로만 이루어진 문자열이 주어질 때, 모든 부분 문자열 중, diverse한 문자열의 개수를 출력해야 한다.

알고리즘

먼저 주어진 문자열에서 1번째 숫자부터 \(k\)번째 숫자 중에서 특정 숫자 \(x\)가 몇 번 나타났는지를 \(cnt[k][x]\)의 형식으로 미리 계산해두면, 특정 문자열이 diverse한 지 10번의 연산안에 계산할 수 있다. 하지만 모든 부분 문자열의 개수가 약 50억개 이므로 이렇게 해도 시간초과가 발생한다.

조금만 생각해보면, diverse한 문자열의 길이는 최대 100인 것을 알 수 있다. 10종류의 모든 숫자가 10번씩 나타나는 경우에 해당한다. 따라서 문자열의 길이가 100 초과인 문자열은 절대 diverse하지 않다.

길이가 100 이하인 모든 부분 문자열의 개수는 최대 1000만 개이므로 이 문자열들에 대해 diverse를 검사하면 제한 시간안에 diverse한 문자열의 개수를 구할  수 있다.

 

C. Zero-Sum Prefixes

code

문제 설명

길이가 \(n\)인 수열의 점수는 다음 조건을 만족하는 1이상 \(n\)이하의 정수 \(i\)의 개수로 정의된다.

 

1번째 원소부터 \(i)번째 원소까지 더한 합이 0이어야 한다.

 

주어진 수열에서 0인 값들은 원하는 값으로 변경할 수 있다. 값들을 적절히 변경할 때, 가능한 수열 점수의 최댓값을 출력해야 한다.

알고리즘

주어진 수열 대신, 주어진 수열의 누적합을 고려해보자. 그렇다면 주어진 수열에서 \(a_i=0\)인 값을 \(x\)로 변경한다는 것은 누적합 배열에서 \(i\)번째 이후의 원소들을 모두 \(x\)만큼 더한다는 것과 동일한 의미가 된다. 그리고 수열의 점수는 누적합 배열에서 값이 0인 원소의 개수가 된다.

값이 0인 원소가 \(N\)개가 있고, \(i\)번째로 등장하는 0인 원소의 위치를 \(p_i\)라 하자. 그렇다면 원래 원소에서 \(p_i\)번째 원소를 \(x\)만큼 어하고, \(p_{i+1}\)번째 원소를 \(x\)만큼 빼서, 누적합에서 \(p_i\)번째 원소부터 \(p_{i+1}-1\)번째 원소까지 \(x\)만큼 더할 수 있다.

누적합의 \(p_i\)번째 원소부터 \(p_{i+1}-1\)번째 원소까지 가장 많이 등장하는 숫자 \(k\)를 찾은 뒤, 해당 범위에 등장하는 숫자를 \(-k\)만큼 더해주자. 그렇다면 누적합에서 0인 원소를 최대한으로 많이 만들 수 있다. 이를 모든 \(i\)에 대해서 실행하고, 누적합에서 0인 원소의 개수를 출력하면 된다.

 

D. ConstructOR

code

문제 설명

1 이상 \(2^{30}\)미만의 숫자 \(a, b, d\)가 주어진다. \(a | x\)와 \(b | x\)가 모두 \(d\)의 배수가 되도록 하는 0이상 \(2^{60\) 이하 \(x\)를 출력해야 한다. 가능한 \(x\)가 여러 개라면 아무거나 출력을 하면 되고, 그렇지 않다면 \(-1\)을 출력해야 한다.

알고리즘

먼저 \(-1\)인 경우를 생각해보자. \(a, b, d\)의 LSB를 고려했을 때, 만약 \(d\)의 LSB보다 \(a, b\)의 LSB가 더 작다면, or 연산을 어떻게 하더라도 or 연산 결과가 \(d\)의 배수가 되도록 할 수 없다.

위 경우에 해당하지 않다면 항상 문제의 조건을 만족하는 \(x\)를 찾을 수 있다. 이는 \(a, b\)값에 관계없이 찾을 수 있다. 먼저 편의를 위해 \(d\)의 LSB가 0이라 하자. 만약 0이 아니라면 0이 될 때까지 2로 나누고, 마지막으로 정답을 출력할 때, 나눈 만큼 곱해서 출력하면 된다.

\(x\)의 0번째 bit부터 29번째 bit까지 모두 켜져있는 \(d\)의 배수를 구할 수 있다. 먼저 \(x = 0\)이라 하고, \(x\)의 0번째 bit부터 29번째 bit의 순서로 보면서 만약 \(x\)의 \(i\)번째 bit가 0이라면, \(x\)에 \(d \times 2^i\)을 더해준다. 그렇다면, \(a|x = b|x = x\)이고 이 \(x\)는 \(d\)의 배수이므로, 이렇게 얻은 \(x\)를 출력하면 된다.

 

E. Yet Another Array Counting Problem

code

문제 설명

길이가 \(n\)이고 각 원소가 1이상 \(m\)이하의 정수인 배열 \(a\)가 주어진다 \(nm \le 10^6\). 특정 배열에서 leftmost maximum을 배열의 가장 큰 값들 중 가장 왼쪽에 있는 원소의 index로 정의하자. 그렇다면 아래 조건을 만족하는 배열 \(b\)의 개수를 구해야 한다.

 

1. 배열 \(b\)의 길이는 \(n\)이고 각 원소는 모두 1이상 \(m\)이하여야 한다.

2. 모든 \(1 \le L < R \le n\)에 대해, a[L:R]과 b[L:R]의 leftmost maximum이 동일해야 한다.

알고리즘

먼저 배열 \(a\)를 이용해 아래 과정을 재귀적으로 반복하여 이진 트리를 만들어보자.

 

1. 배열 \(a[l:r]\)의 Leftmost maximum \(i\)를 찾는다. 현재 노드에 \(a[i]\)를 저장한다.

2. 왼쪽 자식노드를 만들고, 왼쪽 자식노드로 이동해 \(a[l,i-1]\)에 대해서 이 과정을 반복한다.

3. 오른쪽 자식노드를 만들고, 오른쪽 자식노드로 이동해 \(a[i+1, r]\)에 대해서 이 과정을 반복한다.

 

여기서 1번 과정은 세그먼트 트리를 이용하여 \(logN\)안에 처리할 수 있다.

 

이 과정을 반복하면 왼쪽 자식노드는 자신의 값보다 작고, 오른쪽 자식노드는 자신의 값보다 작거나 같게 된다.

만약 트리의 노드에 적힌 값을 변경하더라도, 왼쪽 자식노드가 자신의 값보다 작고, 오른쪽 자식노드가 자신의 값보다 작거나 같으면 이 트리로 만드는 배열 \(n\)가 문제의 조건을 만족하게 된다.

따라서 위 문제는 이렇게 트리를 만들고, 왼쪽 자식노드보다 값이 작고, 오른쪽 자식노드가 값이 작거나 같게 숫자를 할당할 수 있는 경우의 수를 출력하는 문제가 된다.

트리의 각 노드마다 길이가 \(m+1\)인 배열 \(cnt\)를 만들고, \(cnt[i]\)를 현재 노드에 \(i\)이하의 숫자를 할당할 때, 본인이 루트인 서브트리에서 숫자를 할당하는 경우의 수로 정의하자. 왼쪽 자식노드, 오른쪽 자식노드 배열을 \(Lcnt, Rcnt\)라 하자. 그렇다면, \(cnt[i] = Lcnt[i - 1] * Rcnt[i]\)로 계산하고, \(cnt[i]\)배열을 누적합으로 처리하면 \(cnt\)배열을 \(O(m)\)안에 계산할 수 있다.

총 노드의 개수가 \(n\)개이므로, \(O(nm)\)안에 문제를 해결할 수 있다.