Codeforces Round #783 (Div. 1)

Algorithm/Codeforces

Codeforces Round #783 (Div. 1)

이유섭 2022. 4. 22. 13:43

A. Make it Increasing

Problem

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

Problem - A - Codeforces

codeforces.com

n개의 양의 정수를 포함하는 수열 a와 길이가 n인 수열 b가 주어진다. 처음엔 $1 \le i \le n$에 대하여 $b_i = 0$이다.

한 번의 작업에서 너는 하나의 정수 i(1 \le i \le n)을 고를 수 있다. 그리고 $a_i$를 $b_i$에 더하거나 뺄 수 있다. b를 증가수열(모든 원소들이 이전에 나온 원소들보다 정확히 큰 것을 말한다)로 만들기 위해 필요한 작업의 최소 횟수를 구하여라.

Input

첫째 줄에는 하나의 정수 n($2 \le n \le 5000$)가 주어진다.

둘째 줄에는 수열 a의 원소를 의미하는 n개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^9)$이 주어진다.

Output

b를 증가 수열로 만들기 위해 필요한 작업의 최소 횟수를 나타내는 하나의 정수를 출력하여라.

Example

input	output
5 1 2 3 4 5	4
7 1 2 1 2 1 2 1	10
8 1 8 2 7 3 6 4 5	16

Note

예제 1: $a_1$을 $b_1$에 빼고, $a_3, a_4, a_5$를 $b_3, b_4, b_5$에 각각 더해준다. 최종 수열은 4번의 작업 후 [-1, 0, 3, 4, 5]가 될 것이다.

예제 2: 10번의 작업으로 [-3, -2, -1, 0, 1, 2, 3]에 도달할 수 있다.

Tutorial

$O(N^2)$ 풀이이다.

최소 횟수를 구하는 것이기 때문에 정확히 하나의 $b_i$는 건드리지 않고 0으로 두는 것이 가장 좋다. 건드리지 않을 $b_i$가 정해진다면, 우리는 O(N)만에 b가 증가 수열이 되도록 하는 최소 작업 횟수를 구할 수 있다. 즉, 모든 $b_i$에 대해 O(N)의 시간이 걸리기 때문에 최종 시간 복잡도는 $O(N^2)$이 된다.

$b_i$가 0으로 정해졌을 때, b가 증가수열이 되도록 하는 최소 작업 횟수를 구하는 과정을 좀 더 자세히 살펴보자. $i < j \le n$에 대하여 $b_{j-1} < b_j$여야 하며, $b_j$는 $a_j$를 여러 번 더하는 것으로 만들 수 있다. 즉, $b_j$는 $b_{j-1}$ 초과의 가장 작은 $a_j$의 배수가 될 것이다. $1 \le j < i$에 대해서도 똑같이 해주면 된다.

모든 $1 \le i \le n$에 대하여 위의 과정을 거친 후, 최솟값을 찾아 출력해주면 된다.

Solution

#include <bits/stdc++.h>

#define MAXN 5010

using namespace std;

int a[MAXN];

int main()
{
	int n, i, j;
	long long cnt, ans=-1, prev, x;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	
	for(i=0; i<n; i++){
		cnt = prev = 0;
		for(j=i+1; j<n; j++){
			x = prev/a[j] + 1;
			cnt += x;
			prev = x*a[j];
		}
		prev = 0;
		for(j=i-1; j>=0; j--){
			x = prev/a[j] + 1;
			cnt += x;
			prev = x*a[j];
		}
		if(ans==-1 || ans>cnt) ans = cnt;
	}
	
	cout << ans;
	
	return 0;
}

B. Optimal Partition (WA > AC)

Problem

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

Problem - B - Codeforces

codeforces.com

n개의 정수를 포함하는 수열 a가 주어진다. 너는 a를 비어있지 않은 연속된 부분 수열로 나눠야 한다. ($2^{n-1}$가지 방법이 있을 것이다.)

$s = a_l + a_{l+1} + ... + a_r$이라고 하자. 부분 수열 $a_l, a_{l+1}, ..., a_r$의 값은 다음과 같다:

(r - l + 1) if s > 0,
0 if s = 0,
-(r - l + 1) if s < 0.

너가 얻을 수 있는 부분 수열 값의 합 중 최댓값을 구하여라.

Input

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 5 \cdot 10^5$)이 주어진다. 테스트 케이스들에 대한 설명은 다음에 나온다.

각 테스트 케이스의 첫번째 줄에는 하나의 정수 n($1 \le n \le 5 \cdot 10^5$)이 주어진다.

각 테스트 케이스의 두번째 줄에는 n개의 정수 $a_1, a_2, ..., a_n (-10^9 \le a_i \le 10^9)$이 주어진다.

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

Output

각 테스트 케이스에 대하여 너가 얻을 수 있는 부분 수열 값의 합 중 최대 값을 의미하는 하나의 정수를 출력하여라.

Example

input	output
5 3 1 2 -3 4 0 -2 3 -4 5 -1 -2 3 -1 -1 6 -1 2 -3 4 -5 6 7 1 -1 -1 1 -1 -1 1	1 2 1 6 -1

Note

테스트 케이스 1: 최적의 부분 수열 중 하나는 [1, 2], [-3]이다. 1 + 2 >0이므로 [1, 2]의 값은 2이다. -3 < 0이므로 [3]의 값은 -1이다. 2 + (-1) = 1.

테스트 케이스 2: 최적의 부분 수열은 [0, -2, 3], [-4]이고, 값의 합은 3 + (-1) = 2이다.

Tutorial

다양한 방식으로 접근해보았지만, 최종적으로 도달한 것은 DP였다. DP의 전형적인 정의인 "dp[i] = i번째 원소까지 고려했을 때 얻을 수 있는 최댓값"으로 dp[i]를 정의해보았다. 그렇다면 dp[i]를 구하기 위해선 무엇이 필요할까?

dp[i]가 될 수 있는 값들을 생각해보면, (j+1)에서 i까지의 원소 합에 따라 dp[j] + (i - j) 혹은 dp[j] - (i - j)일 것이다. 그렇다면 우리가 해야할 일은 $max(dp[j] \pm (i - j))$을 구하는 것이다. 그러나 이대로라면 시간 복잡도가 $O(N^2)$으로 TLE가 걸릴 것이다. 불필요한 부분을 하나씩 바꿔나가며 식을 간단히 해보자.

우선 dp[j] - (i - j)를 고려할 필요가 없다. 합이 음수인 부분 수열은 전부 쪼개는 것이 낫기 때문이다. 길이가 l인 합이 음수인 부분 수열의 값은 -l 이다. 이는 l개의 원소로 만들 수 있는 가장 작은 점수이며, 이를 전부 쪼개도 값의 합은 -l이거나 이보다 크게 되기 때문이다. 따라서 우리는 합이 음수인 부분 수열 중 길이가 2 이상인 수열은 고려하지 않을 것이다. 즉, 우리는 항상 sum(a[j+1~i])가 양수인 경우에 대해서만 dp[j] + (i - j)를 구할 것이며, a[i]가 음수인 경우 추가로 dp[i-1] - 1을 고려할 것이다.

그럼 이제 우리는 sum(a[j+1~i])가 양수인 경우 dp

DP로 문제를 풀었다. DP의 전형적인 정의인 "dp[i] = i번째 원소까지 고려했을 때 얻을 수 있는 최댓값"으로 dp[i]를 정의해보자. 단순히 dp[i-1]로 답을 구하기 어렵다는 것은 쉽게 알 수 있다. 따라서 $1 \le j < i$인 j를 이용하여 dp[i] 값을 구해보면 $dp[i] = max(dp[j] \pm (i - j))$라는 식을 얻을 수 있다. (j+1부터 i까지의 합이 양수인 경우 +, 음수인 경우 -가 된다.)

여기서 우리는 dp[j] - (i - j)를 고려대상에서 제외시킬 수 있다. 합이 음수인 수열은 길이가 2 이상으로 만들 이유가 없기 때문이다. 즉, 나는 처음부터 길이가 2 이상이며 합이 음수인 수열은 만들 수 없다고 가정하였다. 그렇다면 애초에 위의 식은 만들어질 수가 없다.

이제 우리가 해야 할 일은 sum(a[j+1 ~ i]) > 0인 j에 대하여 max(dp[j] + (i - j))를 구하는 것으로 바뀌었다. i가 1 증가함에 따라 식의 값이 1씩 증가하는 경우. 이러한 방법도 dp를 풀면서 몇번 다뤄봤을 것이다. 바로 dp의 정의를 "dp[i] = i번째 원소까지 고려했을 때 얻을 수 있는 최댓값 + (n - i)"로 바꿔주는 것이다. 굳이 의미를 붙이자면 "i 이후에는 최대 점수를 얻을 수 있다고 가정하고, i번째까지 얻을 수 있는 최댓값" 정도로 해줄 수 있을 것이다. 이렇게 바꾸면 문제를 풀기 쉬운 이유는 다음과 같다.

$
dp[i] := i번째 원소까지 고려했을 때 얻을 수 있는 최댓값 \\
dp'[i] := i번째 원소까지 고려했을 때 얻을 수 있는 최댓값 + (n - i) \\

dp'[i] = dp[i] + (n - i) \\

dp[i] = max(dp[j] + (i - j)) \\
= max(dp[j] + i - j + n - n) \\
= max(dp[j] + (n - j) - (n - i)) \\
= max(dp'[j]) - (n - i) (\because i와 n은 j와 무관)

dp[i] = max(dp'[j]) - (n - i)
dp[i] + (n - i) = max(dp'[j])
dp'[i] = max(dp'[j])
$

즉, 정의를 바꾸면 단순히 앞선 dp값들의 최댓값으로 dp값을 구할 수 있다.

그러나 아직 문제가 하나 남았다. 이전의 모든 값이 고려대상이 아니기 때문이다. i번째까지의 합이 양수인 j에 대해서만 값을 가져와야 하기 때문이다. 이는 인덱스 트리를 이용해 해결하였다. 1번부터 i번까지의 합을 가지고 있는 sum[i]를 미리 구해주면 sum[i] - sum[j]를 통해 j+1부터 i까지의 합이 양수인지를 알 수 있다. 즉, 우리는 sum[j] < sum[i]인 j에 대해서 dp의 최댓값을 구해주면 된다. sum[i]를 말단 노드의 번호로 하는 멕스 인덱스 트리를 만들어 해결할 수 있다. 추가로 sum[i]가 음수가 될 수도, 값이 매우 커질수도 있기 때문에 sum[i]를 리넘버링해서 노드의 번호를 붙여주면 된다.

Solution

#include <bits/stdc++.h>
 
#define MAXN 500010
 
using namespace std;
 
int start;
int a[MAXN], dp[MAXN], tree[4*MAXN];
long long sum[MAXN];
set<long long> s;
map<long long, int> renumber;
 
void insert(int i, int x);
int find_max(int i);
void clear();
 
int main()
{
	int t, n, i, number, tmp;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		s.clear();
		renumber.clear();
		
		cin >> n;
		for(i=1; i<=n; i++){
			cin >> a[i];
			sum[i] = sum[i-1] + a[i];
			s.insert(sum[i]);
		}
		s.insert(0);
		
		number = 0;
		for(auto i: s){
			renumber[i] = number++;
		}
		
		for(start=1; start<n+1; start*=2);
		clear();
		
		dp[0] = n;
		insert(renumber[0], n);
		for(i=1; i<=n; i++){
			if(a[i] > 0) dp[i] = dp[i-1];
			if(a[i] == 0) dp[i] = dp[i-1] - 1;
			if(a[i] < 0) dp[i] = dp[i-1]-2;
			
			auto it = s.lower_bound(sum[i]);
			if(it != s.begin()){
				it--;
				tmp = find_max(renumber[*it]);
				
				dp[i] = max(dp[i], tmp);
			}
			
			insert(renumber[sum[i]], dp[i]);
		}
		
		cout << dp[n] << '\n';
	}
	
	return 0;
}
 
void insert(int i, int x)
{
	i += start;
	
	tree[i] = max(tree[i], x);
	
	i /= 2;
	while(i){
		tree[i] = max(tree[i*2], tree[i*2+1]);
		i /= 2;
	}
}
 
int find_max(int i)
{
	int l=start;
	int maxi=-MAXN;
	
	i += start;
	while(i && l <= i){
		maxi = max(maxi, tree[i]);
		
		if(i%2 == 0) i--;
		i /= 2;
		l /= 2;
	}
	
	return maxi;
}
 
void clear()
{
	for(int i=0; i<2*start; i++) tree[i] = -MAXN;
}

마치며...

저번 코포에서 컨디션이 좋아 좋은 성적을 거뒀다. 덕분에 한 번에 141점이나 오르면서 처음으로 퍼플에 도달하게 되었다. 그리고 이번이 퍼플로써의 첫 코포였다. 코포가 시작하자 자연스레 Div. 1으로 입장이 되었지만 나는 내가 잘못 들어간 줄 알고 Div. 2를 풀기 시작했다. 그리고 20분이 지나서야 퍼플은 Div. 1을 봐야 한다는 사실을 알았다. 뒤늦게 봤지만 다행히 A를 빠르게 풀었고, B의 풀이도 힘들었지만 겨우 생각해냈다. 그.러.나. 풀이가 아무리 생각해도 맞았지만 계속 WA가 나고 결국 나는 블루로 강등당해버렸다. (일회성 퍼플...)

대회가 끝나고 B를 다시 풀어보았다. 그리고 발견한 오류는 "+1을 빼먹었다"였다. 물론 알아내기까지는 여러 번의 테스트가 있었지만 결국 수정한 건 "+1" 두 문자였다. 대회 당시 리넘버링하는 과정에서 sum[0]은 항상 0이기 때문에 set에 0을 추가해야 한다는 것까진 알았지만 이 과정에서 새로 부여된 번호가 0부터 n까지 갈 것이라고 생각하지 못한 게 이유였다 ㅜㅜ

최근에 걱정이 많아 한 가지에 집중을 하지 못하는 것이 결국 이러한 사소한 부분까지 집중을 하지 못하는 데까지 이르렀다는 생각에 하루빨리 멘탈 케어를 해야겠다는 생각을 하였다.