Codeforces Round #827 (Div. 4)

A. Sum

code

문제 설명

세 정수 a, b, c가 주어진다. 한 수가 다른 두 수의 합이 될 수 있는지 여부를 출력하면 된다.

알고리즘

if문을 3번 써서 검사하면 된다.

 

B. Increasing

code

문제 설명

정수로 이루어진 배열이 주어진다. 이 배열의 원소를 잘 재배치해 strictly increasing을 만족하도록 할 수 있는지를 출력하면 된다.

알고리즘

배열을 정렬한 후에 이웃한 원소 중 같은 게 있는지를 보면 된다.

 

C. Stripes

code

문제 설명

8x8의 판에 빨간 가로선과 파란 세로선을 번갈아서 긋는다. 원래 색깔이 있던 칸에 또 칠하면 덮어 씌워진다.

여러 번 색칠한 판의 상태가 주어졌을 때, 마지막으로 칠한 선의 색깔을 출력해야 한다.

알고리즘

빨간 선과 파란 선은 각각 가로, 세로로 정해져 있다. 즉, 파란 선을 그으면 빨간 선은 무조건 덮어 씌워진다. 따라서 중간에 끊어지지 않은 빨간 가로선이 존재하면 빨간 선을 마지막으로 칠한것이고, 그렇지 않다면 파란 선을 마지막으로 칠한 것이다.

 

D. Coprime

code

문제 설명

최대 길이 200,000이고 각 원소는 최대 1,000인 자연수 배열이 입력으로 주어진다.

이 때, 서로소 \(a_i\), \(a_j\)에 대해 가능한 \(i+j\)의 최댓값을 구해야 한다.

알고리즘

단순히 \(O(n^2)\)으로 모든 수를 검사해보려 하면 시간초과가 나게 된다. 따라서 원소의 입력이 작다는 점을 활용해야 한다.

먼저 1부터 1,000까지 총 1,000종류의 숫자가 존재하고, 이를 쌍으로 묶으면 \(\binom{1000}{2}\)개의 쌍이 존재한다.

따라서 약 500,000개의 쌍 중 gcd 알고리즘을 이용하여 coprime인 쌍을 먼저 골라낸다.

 

그 후, 배열이 입력으로 들어올 때, 1이상 1,000까지 수에 대해 최대 index를 구한다. 그리고 모든 coprime 쌍에 대해 index가 존재한다면, index의 합을 계산한 뒤 max값을 갱신하여 답을 구해준다.

E. Scuza

code

문제 설명

길이가 최대 200,000인 자연수 배열이 주어진다.

배열의 \(i\)번째 값은 \(i\)번째 계단의 높이를 의미한다. 즉 \(i-1\)번째 계단과 \(i\)번째 계단의 높이 차를 의미한다. 0번째 계단은 높이가 0인 지면이다.

다리의 길이를 \(k\)라 할 때, 다리의 길이보다 높은 계단은 오를 수 없다. 총 \(q\)개의 쿼리가 주어진다. 각 쿼리에서는 다리의 길이 \(k\)가 주어질 때, 오를 수 있는 계단의 총 높이를 출력해야 한다.

 

알고리즘

먼저 최대로 오를 수 있는 계단 번호를 구해보자. 1번째 계단의 높이가 7이고, 2번째 계단의 높이가 5라고 하자. 그렇다면 그냥 2번째 계단의 높이를 7이라 가정하고 풀어도 오를 수 있는 계단 번호는 바뀌지 않는다. 1번째 계단을 넘었다는 것은 높이가 7 이하인 계단을 모두 넘을 수 있다는 것이므로, 2번째 계단의 높이를 7로 바꿔도 영향이 없다. 따라서 계단 배열 \(a[i]\)를 \(a[i] = max(a[i], a[i - 1]\)의 점화식으로 갱신을 한 뒤에 고려해보자.

 

배열을 위 식을 이용해서 갱신하면 위 배열은 오름차순이 된다. 따라서 다리의 길이가 \(k\)일 때, 오를 수 있는 계단 번호를 lower_bound를 이용해서 찾을 수 있다. 계단의 높이는 입력받을 때 미리 누적합으로 전처리하면 오를 수 있는 계단의 높이도 바로 구할 수 있다.

 

F. Smaller

code

문제 설명

맨 처음에 알파벳 a 하나만 가지고 있는 두 문자열 \(s\), \(t\)가 있다.

이 문자열에 대해 쿼리를 처리해야 한다.

각 쿼리에서는 두 문자열 중 한 문자열에 특정 문자열 \(x\)를 \(k\)번 뒤에 추가한다.

문자열을 추가한 후, 두 문자열을 재배열하여 \(s\)가 \(t\)보다 사전순으로 앞설 수 있는지를 출력해야 한다.

 

알고리즘

먼저 \(s\), \(t\)의 실제 문자열을 저장하려고 하면 시간과 메모리가 모두 부족하다. 각 문자열은 재배열할 수 있으므로, 메모리와 시간 절약을 위해 \(s\), \(t\) 문자열의 각 문자의 개수만 저장해서 관리해도 된다.

따라서 각 쿼리에 대해 \(x\) 문자열에 있는 각 문자의 개수를 구하고, 이를 \(k\)배 하여 \(s\)나 \(t\) 문자열의 문자 개수에 추가하면 된다.

 

이제 문자의 개수만으로 문자열을 사전순으로 \(s\)가 \(t\)보다 먼저 올 수 있는지를 검사해야 한다.

\(s\)는 사전순으로 최대한 빨라야 하므로, a-z 순서로 배열하고, \(t\)는 사전순으로 최대한 느려야 하므로 z-a 순서로 배열해야 한다.

각 문자의 개수를 저장해두었으므로, 이를 이용하여 배열 결과 \(s\)가 \(t\)보다 사전순으로 빠르게 재배열할 수 있는지를 검사하면 된다. 자세한 검사 방식은 위 코드의 test()함수에 구현해 두었다.

 

G. Orray

code

문제 설명

길이가 최대 200,000인 배열 \(a\)가 주어진다. 이제 이 배열을 이용하여 새로운 배열 \(b\)를 정의한다. \(b_i\)는 \(a_1\)부터 \(a_i\)까지의 모든 원소를 or 연산한 값으로 정의한다. 배열 \(b\)가 사전 순으로 가장 느리도록 배열 \(a\)를 재배열해야 한다.

알고리즘

\(b[i]\)와 \(b[i+1]\)의 값을 비교해보자. 만약 두 값이 다르다면, \(b[i+1]\)는 \(b[i]\)의 꺼져있는 bit 중 일부가 켜져있는 꼴일 것이다. \(b[i+1] = b[i] OR a[i+1]\)이기 때문이다.

bit의 개수는 최대 32개이기 때문에 \(b[i] < b[i+1]\)인 경우는 최대 32번만 존재한다는 것을 알 수 있다. 또한 꺼진 bit는 최대한 빨리 키는 것이 이득이므로, 앞의 최대 32개의 원소 \(b[i]\)만 다르고, 그 뒤의 원소는 모드 동일하다는 것을 알 수 있다. 이를 이용하면 \(a\)배열에서 최대 32개의 원소만 잘 선택하면, 나머지 원소는 아무거나 선택해도 된다.

 

이제 \(b[i]\)가 최대가 되도록하는 \(a[i]\)를 잘 선택하는 알고리즘을 생각해보자. 먼저 \(b[i-1]\)에 대해, \(b[i-1]\)에서 꺼져있는 bit를 키는 것이 중요하다. 이미 켜져있는 bit는 \(a[i]\)값에 관계없이 계속 켜져있기 때문이다. 따라서 \(b[i-1]\)의 꺼져있는 bit만 고려하기 위해 \(a\)배열의 모든 원소에 다음 연산을 취한다. \( (a = a - b[i-1] \& a) \)

이제 \(a\)배열 중 가장 큰 값을 선택하면 \(b[i]\)값이 최대가 된다. 이를 32번만 반복해서 배열 \(a\)의 32개의 원소를 재배열하고 남은 원소는 아무렇게나 그 뒤애 재배열하면 된다.