Codeforces Round #835 (Div. 4)

A. Medium Number

code

문제 설명

3개의 수를 입력받아 중앙값을 출력해야 한다.

알고리즘

세 수를 정렬하고, 2번째 숫자를 출력하였다.

 

B. Atilla's Favorite Problem

code

문제 설명

주어진 문자열을 적을 때, 1번째 알파벳인 a부터 몇 번째 알파벳까지 사용해야 하는지를 출력해야 한다.

알고리즘

문자열 \(s\)에 있는 모든 문자 \(c\)에 대해 \(c - 'a' + 1\)의 최댓값을 출력하면 된다.

 

C. Advantage

code

문제 설명

길이가 \(n\)이고 각 원소가 정수인 배열이 주어진다. 모든 원소에 대해 자신에서 자신을 제외한 값들 중 최대인 값을 뺀 결과를 구해 출력해야 한다.

알고리즘

먼저 최댓값을 가지는 원소를 하나 찾는다. 해당 원소를 제외한 원소들은 자신에서 최댓값을 빼서 문제의 값을 구할 수 있다. 최댓값을 가지는 원소는 자신을 제외한 나머지 값들의 최댓값을 \(O(n)\)에 naive하게 구해서 문제의 값을 구한다.

 

D. Challenging Valleys

code

문제 설명

길이가 \(n\)이고 각 원소가 정수인 배열이 주어진다. 특정 구간 (l, r)에 대해서 l번 원소부터 r번 원소까지는 모두 동일하며, l-1번 원소는 없거나 l번 원소보다 커야 하고, r+1번 원소 또한 없거나 r번 원소보다 큰 (l, r) 구간이 유일하게 하나 존재하면 해당 배열은 valley이다. 주어진 배열이 valley인지를 판단해야 한다.

알고리즘

먼저 주어진 배열에서 최솟값을 가지는 원소를 하나 찾는다. 이후 이 원소 왼쪽에 있는 모든 \(i\)번째 원소에 대해서 \(a_i > a_{i+1}\)을 만족해야 하고, 이 원소 오른쪽에 있는 모든 \(i\)번째 원소에 대해서 \(a_i > a_{i-1}\)을 만족하는 지 확인한다. 만약 모든 원소가 이를 만족한다면 해당 배열은 valley이다.

 

E. Binary Inversions

code

문제 설명

0또는 1로만 이루어졌고 길이가 \(n\)인 배열이 주어진다. 이 배열에서 inversion의 수는 \(1\le i < j \le n\)이면서 \(a_i = 1, a_j = 0\)인 \((i, j) \)의 개수이다. 이 배열에서 최대 1개의 값을 변경하여 만들 수 있는 inversion의 최대 개수를 구해야 한다.

알고리즘

누적 합을 이용하여 1번 원소부터 \(k\)번 원소까지 0인 원소와 1인 원소의 개수를 구해놓으면, 특정 구간의 0의 개수와 1의 개수를 \(O(1)\)안에 구할 수 있다. 이를 이용하면 숫자를 바꾸지 않은 원래 배열에서 inversion의 개수를 \(O(n)\)안에 구할 수 있다. 값이 1인 모든 원소에 대해서 오른쪽에 있는 0의 개수를 모두 더해주면 된다.

 

이제 특정 원소를 바꿀 때 inversion이 어떻게 변하는 지를 계산해야 한다. 만약 특정 원소를 0에서 1로 바꾼다면, inversion은 자신 왼쪽에 있는 1의 개수만큼 줄어들고, 자신 오른쪽에 있는 0의 개수만큼 증가한다. 또한, 특정 원소를 1에서 0으로 바꾼다면 inversion은 자신 왼쪽에 있는 1의 개수만큼 증가하고, 자신 오른쪽에 있는 0의 개수만큼 증가한다. 따라서 특정 원소를 바꾸었을 때, inversion 개수의 변화를 \(O(1)\)에 계산할 수 있다.

 

모든 원소에 대해 바꾸었을 때, inversion 개수의 변화를 계산한 뒤, 그 중 최댓값을 출력하면 된다. 이때, 아무 원소도 바꾸지 않는 경우고 고려해야 함을 주의해야 한다.

 

F. Quests

code

문제 설명

총 \(n\)개의 퀘스트가 있고 \(i\)번째 퀘스트를 깨면 \(a_i\)개의 코인을 받는다. \(i\)번째 퀘스트를 깬 후에는 \(k\)일동안 해당 퀘스트를 깰 수 없다.

 

총 \(d\)일동안 최소 코인을 \(c\)만큼 얻고자 할 때, 가능한 \(k\)의 최댓값을 출력해야 한다. 만약 어떤 \(k\)값에 대해서도 코인을 \(c\)만큼 모을 수 없다면 Impossible을, 무한히 큰 \(k\0값에 대해서도 코인을 \(c\)만큼 모을 수 있다면 Infinity를 출력해야 한다.

 

알고리즘

가장 먼저 Impossible인 case와 Infinity인 case를 처리하자. 가장 많은 코인을 얻을 수 있는 퀘스트를 \(d\)번 깨도 \(c\)개 이상의 코인을 얻을 수 없다면 Impossible이다. 또한, 모든 퀘스트를 종류별로 최대 1번씩만 깨고, 총 \(d\)개만 깨도 \(c\)개 이상의 코인을 얻을 수 있다면 Infinity이다. 이 경우들은 미리 처리해두자.

 

이제 주어진 \(k\)가 파라매트릭 서치 조건을 만족한다는 것을 확인해야 한다. 만약 특정 \(k\)에 대해서 \(d\)일동안 \(c\)개 이상의 코인을 모으는 방법이 있다고 하자. 그렇다면 \(k\)가 더 작은 경우에는 똑같은 방법을 따라서 \(c\)개 이상의 코인을 모을 수 있다. 따라서 주어진 문제는 파라매트릭 서치 조건을 만족한다.

 

그러면 특정 \(k\)에 대해 \(d\)일동안 \(c\)개 이상의 코인을 모을 수 있는지 확인하자. 일단 한 번 깬 퀘스트는 \(k\)일동안 깰 수 없으므로, \(n\)개의 퀘스트 중 많은 코인을 주는 \(k+1\)개의 퀘스트를 고른 뒤 이를 번갈아가면서 \(d\)일동안 깨면 된다.따라서 각 퀘스트를 먼저 \(\frac{d}{k+1}\)만큼 깨고, 남은 시간동안 \(k+1\)개의 퀘스트 중 코인을 많이 주는 순서대로 퀘스트를 선택하면 된다.

 

\(k\)값이 최소 0, 최대 \(d\)이므로, 해당 범위에서 파라매트릭 서치를 시행하여 위 조건을 만족하는 최대인 \(k\)를 구할 수 있다.

 

G. SlavicG's Favorite Problem

code

문제 설명

총 \(n\)개의 정점으로 구성된 가중치가 있고 방향이 없는 트리가 주어진다. 이제 \(a\)번 점에서 \(b\)번 점까지 이동할 예정이다.

 

현재 0으로 초기화 되어있는 \(x\)가 있어, 특정 간선을 사용해 이동할 때마다 간선에 있는 값이 \(x\)에 XOR된다.

 

\(b\)번 정점을 제외한 정점은 언제든지 방문할 수 있지만, \(b\)번 정점은 도착할 때 \(x\)가 0이 되는 경우에만 방문할 수 있다.

 

최대 1번, 어디서든 워프를 사용해서 \(b\)번 정점을 제외한 모든 정점으로 이동할 수 있다.

 

\(a\)번 정점에서 \(b\)번 정점으로 이동할 수 있는지 여부를 출력해야 한다.

 

알고리즘

\(a\)번 정점에서 \(b\)번 정점으로 가는 과정을 크게 세 과정으로 구분할 수 있다. \(a\)번 정점에서 \(u\) 번 정점으로 이동하는 과정, \(u\)번 정점에서 \(v\)번 정점으로 워프하는 과정, \(v\)번 정점에서 \(b\)번 정점으로 이동하는 과정 이렇게 세 과정으로 구분된다.

 

\(u\)번 정점에서 \(v\)번 정점으로 워프하는 동안에는 \(x\)의 값이 변하지 않는다. 따라서 \(a\)번에서 \(u\)번 정점으로 이동하는 경로들의 XOR값과 \(v\)번 정점에서 \(b\)정점으로 이동하는 경로들의 XOR값이 동일해야 한다.

 

따라서 \(a\)번 정점으로부터 \(b\)번 정점을 도달하지 않고 갈 수 있는 모든 정점까지의 XOR 값을 \(v1\) 배열에 저장하고, \(b\)번 정점으로부터 모든 정점까지의 XOR값을 \(v2\)배열에 저장한다. 이후, 만약 \(v1\)과 \(v2\)에 똑같은 값이 하나라도 존재한다면, \(a\)번 정점에서 \(b\)번 정점까지 도달할 수 있는 것이다.

 

총평

F를 1번, G를 2번 틀렸다. Div 4인 만큼 문제가 쉬울 것이라 예상하고 코드를 너무 성급하게 제출해서 실수가 많았던 것 같다. G번의 경우에는 문제가 무슨 뜻인지 이해하지 못해서 두 세번 정도 읽었던 것 같다. Div4라 그런지 흥미로운 문제는 없었던 것 같다. 그럼에도 불구하고 쉬운 문제를 빨리 푸는 법을 익히기 위해 DIv4도 꾸준히 참가하고 있다.

 

7문제를 푸는 데 약 50분이 걸리고 있지만, 계속 연습해서 30분 선 안으로 컷하는 연습을 해야할 것 같다.