Algorithm/Codeforces

Codeforces Round #782 (Div. 2)

이유섭 2022. 4. 19. 00:34

Problems
Submissions
Standing
Rating

 

 

A. Red Versus Blue

Problem

https://codeforces.com/contest/1659/problem/A

 

Problem - A - Codeforces

 

codeforces.com

 레드팀과 블루팀이 FPS 게임에 참가했다. 그들의 경기는 전세계에 중계되었다. 그들은 n경기를 진행했다.

 

 그 결과, 레드팀은 r번, 블루팀은 b번 이겼다. 블루팀은 레드팀보다 실력이 부족하다, 그래서 b는 r보다 정확히 작다.

 

 너는 자느라 중계를 놓쳤다. 그러나 너는 많은 사람들이 중계를 봤기에 경기가 막상막하였을 것이라 생각한다. 그래서 너는 i번째 문자가 i번째 경기에서 이긴 팀을 나타내는 길이가 n인 하나의 문자열을 생각해보았다. 만약 문자가 R이면 레드팀이 이겼음을, 문자가 B이면 블루팀이 이겼음을 의미한다. 너는 문자열에서 한 팀이 연속으로 이긴 횟수의 최댓값이 가능한 작도록 문자열을 생각하려고 한다. 예를 들어, RBBRRRB라면, 레드팀이 역속으로 3번 이겼으며, 이것이 최대이다.

 

 너는 위의 조건을 만족하는 문자열을 찾고자 한다. 만약 답이 여러개라면 아무거나 출력하여라.

 

 

Input

 첫번째 줄에는 테스트 케이스의 수를 의미하는 하나의 정수 t($1 \le t \le 1000$)가 주어진다.

 

 각 테스트 케이스는 3개의 정수 n, r, b($3 \le n \le 100; 1 \le b < r \le n, r+b = n$)를 포함하는 하나의 줄을 가진다.

 

 

Output

 각각의 테스트 케이스에 대하여 주어진 조건을 만족하는 하나의 문자열을 출력하여라. 만약 답이 여러개라면 아무거나 출력하여라.

 

Example

input output
3
7 4 3
6 5 1
19 13 6 		RBRBRBR
RRRBRR
RRBRRBRRBRRBRRBRRBR
6
3 2 1
10 6 4
11 6 5
10 9 1
10 8 2
11 9 2 		RBR
RRBRBRBRBR
RBRBRBRBRBR
RRRRRBRRRR
RRRBRRRBRR
RRRBRRRBRRR

 

 

Tutorial

 b가 항상 r보다 작으므로 b를 기준으로 r을 나눠주면 된다. 즉, r개의 R을 (b+1)개로 나눠주고 그 사이에 B를 넣어주면 된다. 이때 단순히 R을 $\lceil {r \over b+1} \rceil$ 개씩 일정하게 출력하다 마지막에 남는 R을 출력하는 오류를 범하지 않게 주의하자. (n=20, a=11, b=9)이 반례가 될 수 있다.

 

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t, n, r, b, i, j;
	
	cin >> t;
	while(t--){
		cin >> n >> r >> b;
		
		for(i=0; i<b; i++){
			for(j=0; j<r/(b+1-i); j++) cout << 'R';
			cout << 'B';
			
			r -= r/(b+1-i);
		}
		for(j=0; j<r; j++) cout << 'R';
		cout << '\n';
	}
	
	return 0;
}

 

 

B. Bit Flipping

Problem

https://codeforces.com/contest/1659/problem/B

 

Problem - B - Codeforces

 

codeforces.com

 길이가 n인 이진 문자열이 주어진다. 너는 정확히 k번의 작업을 할 수 있다. 한번의 작업에서, 너는 하나의 비트를 골라야 한다. 그 작업에서는 고른 비트를 제외한 모든 비트들이 뒤집힌다(0은 1, 1은 0이 된다). 모든 k번의 작업을 수행한 후, 너가 얻을 수 있는 사전적으로 가장 큰 문자열을 알아내어라. 그리고, 각각의 비트들을 몇번 골랐는지도 출력하여라. 만약 답이 여러개라면 아무거나 출력하여라.

 

 같은 길이에서 이진 문자열 a가 이진 문자열 b보다 사전적으로 크다는 것은 다음을 의미한다:

  • a와 b가 처음으로 다른 위치에서, 문자열 a에 1이 있고, 문자열 b에 0이 있다.

 

 

Input

 첫째 줄에는 테스트 케이스의 수를 의미하는 하나의 정수 t($1 \le t \le 1000$)가 주어진다.

 

 각 테스트 케이스는 2개의 줄을 가진다. 첫째 줄은 2개의 정수 n과 k($1 \le n \le 2 \cdot 10^5; 0 \le k \le 10^9$)가 주어진다.

 

 두번째 줄에는 0과 1로 이루어진 길이가 n인 이진 문자열이 주어진다.

 

 모든 테스트케이스에 대하여 n의 합은 $2 \cdot 10^5$을 넘지 않는다.

 

 

Output

 각각의 테스트 케이스에 대하여, 2개의 줄을 출력하여라.

 

 첫째 줄에는 너가 얻을 수 있는 사전적으로 가장 큰 문자열을 출력하여라.

 

 둘째 줄에는 n개의 정수 $f_1, f_2, ..., f_n$을 출력하여라. $f_i$는 i번째 비트가 선택된 횟수를 의미한다. 이 수들의 합은 반드시 k와 같아야 한다.

 

 

Example

input output
6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110 		111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4

 

 

Tutorial

 우선 k의 범위를 보면 최대 $10^9$으로 뒤집는 순서가 그리 중요하지 않을 것이라는 것을 직감할 수 있을 것이다.

 

 그렇다 우리는 순서는 중요하지 않고, 각 비트들이 몇번 뒤집히는지만 알면 된다. i번째 비트는 ($k - f_i$)번 뒤집히게 될 것이다. 그러나 뒤집히는 작업의 특성상 ($k - f_i$)번 뒤집히는 것은 ($k + f_i$)번 뒤집는 것과 같다는 것을 알 수 있을 것이다. 즉, 우리는 우선 모든 비트를 k번 뒤집어놓고 시작할 것이다. 그러나 마찬가지로 뒤집는 작업의 특성상 2번 뒤집는 행위는 의미 없는 행위임을 알 수 있고, 따라서 k가 홀수면 주어진 수열을 뒤집고, 그렇지 않으면 주어진 수열을 그대로 둠으로써 k번 뒤집는 것과 같은 작업을 할 수 있다.

 

 이제 우리는 수열이 최대가 되도록 각 비트들을 뒤집어주면 된다. 사전순으로 가장 큰 수열을 만들기 위해서는 앞에서부터 최대한 1이 많이 나와야 된다. 즉, 앞에서부터 살펴보면서 0이 나오면 해당 비트를 뒤집어 주는 작업을 통해 수열을 최대한 크게 만들 수 있다. 이는 모든 0을 다 뒤집거나, 뒤집는 횟수를 다 쓸 때까지 반복한다.

 

 만약 모든 비트를 1로 만들었음에도 불구하고 뒤집는 횟수가 남아 있다면, 마지막 비트에 뒤집는 횟수를 전부 넣어줌으로써 답을 구할 수 있다. (당연히 남은 횟수가 홀수이면 마지막 비트를 뒤집어줘야 한다. 아마 0으로 바뀔 것이다.)

 

 

Solution

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

int arr[MAXN], cnt[MAXN];

int main()
{
	int t, n, k, i;
	string str;
	
	cin >> t;
	while(t--){
		cin >> n >> k;
		cin >> str;
		
		for(i=0; i<n; i++){
			arr[i] = str[i]-'0';
			if(k%2 == 1) arr[i] = 1-arr[i];
			
			cnt[i] = 0;
		}
		
		for(i=0; i<n && k>0; i++){
			if(arr[i] == 0){
				cnt[i] = 1;
				arr[i] = 1;
				k--;
			}
		}
		
		cnt[n-1] += k;
		if(k%2 == 1) arr[n-1] = 1-arr[n-1];
		
		for(i=0; i<n; i++) cout << arr[i];
		cout << '\n';
		for(i=0; i<n; i++) cout << cnt[i] << ' ';
		cout << '\n';
	}
	
	return 0;
}

 

 

C. Line Empire

Problem

https://codeforces.com/contest/1659/problem/C

 

Problem - C - Codeforces

 

codeforces.com

 

 

Tutorial

 가장 먼저 깨달아야 할 점은, 만약 성을 움직일 일이 있다면 미리미리 움직이자는 것이다.

 

 이를 스스로 깨달을 정도라면 이 문제는 그리 어렵지 않다. 성을 i번까지만 옮기고 모든 거점을 점령한다고 가정해보자. 이 경우 모든 거점을 점령하는 비용은 다음과 같을 것이다.

 

  • i번째 거점까지 점령하는 비용
    • $1 \le j \le i$인 모든 j에 대하여 점령하고, 성을 옮기고를 반복한다.
$
\sum_{j=1}^i b \times |x_j - x_{j-1}| + a \times |x_j - x_{j-1}| \\
= \sum_{j=1}^i (a+b) \times |x_j - x_{j-1}| \\
= (a+b) \cdot x_i
$

 

  • i+1번째 거점부터 n번째 거점까지 점령하는 비용 
    • $i < j \le n$인 모든 j에 대하여 성이 $x_i$에 위치한채 거점 점령
$
\sum_{j=i+1}^n b \times |x_j - x_i| \\
= \sum_{j=i+1}^n b \times |x_j - x_{j-1}| \times (n-j+1)
$

 

 사실 i번째 거점까지 점령하는 비용은 그리 어렵지 않았겠지만, i+1번째 거점부터 n번째 거점까지 점령하는 비용에서 막혔을 것이다. 언뜻 봐서는 모든 i에 대하여 O(N)의 시간복잡도가 걸리는 것처럼 보이기 때문이다. 그러나 위와 같이 식을 변형시켜주면 우리는 i를 n부터 1까지 살펴보면 i+1번째 거점부터 n번째 거점까지 점령하는 비용을 이전 값을 이용하여 O(1)만에 구해줄 수 있다.

 

 

Solution

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

long long x[MAXN];

int main()
{
	int t, n, a, b, i;
	long long mini, sum, cost;
	
	cin >> t;
	while(t--){
		cin >> n >> a >> b;
		for(i=1; i<=n; i++){
			cin >> x[i];
		}
		
		mini = x[n] * (a+b);
		sum = 0;
		for(i=1; i<=n; i++){
			sum += (x[n-i+1] - x[n-i]) * i;
			cost = x[n-i] * (a+b) + sum * b;
			
			mini = min(mini, cost);
		}
		
		cout << mini << '\n';
	}
	
	return 0;
}

 

 

D. Reverse Sort Sum

Problem

https://codeforces.com/contest/1659/problem/D

 

Problem - D - Codeforces

 

codeforces.com

 

 

Tutorial

 이런 문제는 앞 혹은 뒤에서부터 원본 값을 확정지어 나가는 방식으로 해결할 수 있다. 이 문제는 뒤에서부터 값을 확정하는 방식으로 문제를 해결하였다. 또한 주어진 데이터를 원본 데이터로 어떻게 표현 할 수 있을지 생각해보면 그 식을 역으로 사용해 원본 데이터를 구하는데 사용할 수 있다.

 

 $B_i$를 만들 때 정렬만 하기 때문에 1의 총 개수에는 변함이 없다. 이를 통해 우리는 주어진 C로부터 원래 A에 있는 1의 총 개수를 알 수 있다. 그리고 이를 통해 우리는 $B_n$을 알 수 있다.

 

 C[n]의 값을 A와 $B_n$으로 나타내면 다음과 같을 것이다.

$
C[n] = (n-1) \times A[n] + B_n[n]
$

 즉, A[n]은 다음과 같이 쓸 수 있다.

$
A[n] = {C[n] - B_n[n] \over n-1}
$

 

 그럼 이제 $B_{n-1}$이 어떻게 생겼을지 생각해보자. $B_{n-1}$은 $B_n$으로부터 만들 수 있다. 만약 A[n]이 0이라면 $B_{n-1}$은 $B_n$에서 0이 빠진 형태일 것이고, A[n]이 1이라면 $B_{n-1}$은 $B_n$에서 1이 빠진 형태일 것이다. 그러나 여기서 주목할 점은 A[n]이 0일 때이다. B에 있는 1들을 보면 1이 빠질 때는 가만히 있지만 0이 빠지면 1들이 마치 앞으로 이동하는 것처럼 보인다(그리고 절대 뒤로 이동하는 일은 없다). 잠깐 n이 아닌 다른 i들에 대하여 A[i] 값을 생각해보자.

$
C[i] = (i-1) \times A[i] + \sum_{j=i}^n B_j[i]\\
A[i] = {C[i] - \sum_{j=i}^n B_j[i] \over i-1}
$

 이전에는 간단해보였던 식이 $B_j$ 때문에 복잡해졌다. 즉, 우리는 A[i]를 구하기 위해선 $\sum_{j=i}^n B_j[i]$ 를 구해줘야 한다. 여기서 A[n]이 0일 때를 주목하라는 이유가 나온다. 어느순간 $B_k[i]$가 1이 되면 이후 모든 $i \le j \le k$인 j에 대하여 $B_j[i]$가 1이 되기 때문이다. 즉 우리는 $B_j[i]$가 1이 되는 j를 찾아주기만 하면 되고, 그 값을 $k_i$라고 하면 우리는 위의 식을 다음과 같이 쓸 수 있게 된다.

$
A[i] = {C[i] - (k_i-i+1) \over i-1}
$

 

 그리고 $k_i$는 $B_x$에 포함된 0의 개수에 대한 정보를 통해 알아낼 수 있다.

 

 추가로 유효한 입력만이 들어오기 때문에 $C[i] - (k_i-i+1)$ 값은 항상 0 혹은 (i-1)이며, 따라서 $C[i] - (k_i-i+1)$ 값이 0인지 아닌지를 통해 A[i]를 결정할 수 있다. 또한 i가 1인 경우 (i-1)이 0이 되어 위의 식을 사용하지 못한다. 따라서 A[1]의 숫자는 C[1]이 0인지 아닌지를 통해 알아낼 수 있다.

 

 

Solution

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

int a[MAXN], c[MAXN], last[MAXN];

int main()
{
	int t, n, i, zeros;
	long long sum;
	
	cin >> t;
	while(t--){
		cin >> n;
		
		sum = 0;
		for(i=0; i<n; i++){
			cin >> c[i];
			sum += c[i];
			
			last[i] = a[i] = 0;
		}
		
		zeros = n - sum/n;
		for(i=zeros; i<n; i++){
			last[i] = n;
		}
		
		for(i=n-1; i>=0; i--){
			if(zeros == i+1) break;
			
			if(c[i] == last[i]-i) a[i] = 0;
			else a[i] = 1;
			
			if(a[i] == 0){
				zeros--;
				if(zeros>=0) last[zeros] = i;
			}
		}
		if(c[0] > 0) a[0] = 1;
		
		for(i=0; i<n; i++) cout << a[i] << ' ';
		cout << '\n';
	}
	
	return 0;
}

 

 

마치며...

 오늘 코포 덕분에 하루를 행복하게 시작했다. 최근 D를 풀어내지 못해 레이팅이 1800 아래로 떨어져 있었다. 어제 코포를 풀면서 D까지 거의 1시간 만에 풀기는 했지만 결국 E를 풀어내지 못해 레이팅에 큰 기대를 하고 있지 않았었다(실제로 레이팅이 100점 이상 오른적이 없었다). 그러나 오늘 아침 결과를 확인하는 순간!!! 레이팅이 141점이나 오르면서 처음으로 퍼플에 들어갔기 때문이다!!! 글을 쓰고 있는 지금 하루를 그리 알차게 보내진 않았지만 그래도 시작만큼은 너무나도 행복하게 시작한 하루였다.

 

 추가로 나는 원래 글을 쓰는 것을 별로 좋아하지 않는다. 배운 것을 정리하는 것은 더욱 그렇다. 지식을 머릿 속에 넣는 것을 중요시 여기기에 글을 쓰는 것을 시간낭비라고 생각하기 때문이다(가끔은 정리하는데 시간이 더 많이 걸려 배보다 배꼽이 더 크다는 생각을 적잖게 했다). 최근에는 글로 남기는 것의 중요성을 깨닫고 열심히 쓰는 중인데 코포 정리할 때마다 문제 해석을 같이 적을까를 매번 고민하게 된다. 정작 대회 당시에는 모르는 단어를 넘기며 의미만 파악하는데 글을 정리할 때 이 문장을 해석하고 있으니 시간 낭비라는 생각이 가끔 들기 때문이다. 오늘도 중간부터 문제 해석을 안했는데 다음부터 어떻게 글을 정리할지 고민해봐야겠다.