배치 다섯째 판

대회 요약

스코어보드

 이번에는 Hello 2024로, 모든 사람을 대상으로 Rated였다.

대회 시간이 2시간 30분이었는데, 무려 2시간 21분동안 한 문제도 못풀었고, 제출도 한번도 못해봤다.

여느 때처럼 A, B를 10분동안 밀고, C를 봤는데 풀이가 안 떠올라서 일단 E로 넘어갔다.

 

E는 경우의 수 문제였고, 대충 n^2스위핑으로 풀릴 것 같아서 풀다가, 생각해야 할 경우가 좀 많아서 결국 구현을 못하고 대회가 끝났다. 아무리 점수가 높아도 쉬운 문제를 거르고 어려운 문제를 푸는 것은 아직 욕심인 것 같고, 다음 대회때는 반드시 쉬운 문제들은 풀고 넘어가야 할 것 같다.

 

깔끔하게 A, B만 풀고 대회를 종료하니 한 8000등 정도를 했는데, 레이팅은 딱 1점 떨어졌지만, 원래 5번째 판에는 100점을 주므로 실질적으로는 -101점이다. C만 풀었어도 파란색이 됐을 것 같아서 약간 더 아쉬운 것 같다.

 

A. Wallet Exchange

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
 
#include <iostream>
 
using namespace std;
 
int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
 
	int T;
	cin >> T;
 
	for (int tc = 0; tc < T; tc++) {
		int a, b;
		cin >> a >> b;
 
		if ((a + b) % 2 == 0) {
			cout << "Bob" << '\n';
		}
		else {
			cout << "Alice" << '\n';
		}
	}
 
	return 0;
}
 
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

A는 게임 이론 문제였는데, 그냥 출력 예시 보고 이렇게 하면 되겠다 하고 바로 짜서 맞았다.

기본적으로 각 턴에 지갑을 교환할 수 있으므로, Bob이나 Alice의 지갑 중 하나라도 돈이 남아있다면 현재 턴의 플레이어는 패배하지 않는다. 그리고 각 턴에서 동전을 무조건 하나씩 가져가므로, 두 지갑의 동전 개수 합이 홀수개라면 마지막 동전을 Alice가, 짝수개라면 Bob이 승리한다. a, b가 모두 10억 이하이므로 a + b도 int범위 안이고, 오버플로우를 걱정할 필요는 없다.

 

B. Plus-Minus Split

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
 
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
 
	int T;
	cin >> T;
 
	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;
		string s;
		cin >> s;
 
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '+') {
				res++;
			}
			else {
				res--;
			}
		}
 
		cout << abs(res) << '\n';
	}
 
	return 0;
}
 
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

B는 주어진 집합을 여러 부분으로 나누었을 때 문제에서 주어진 p값의 합을 중 최소값을 구하는 최적화 문제이다.

집합을 나눌 때, 어떤 부분의 값은 다른 부분의 값에 영향을 미치지 않으므로 이미 나뉜 부분을 더 나눠서 p값이 줄어든다면, 그렇게 하는 것이 최선이다. 이 관찰을 통해서 그리디하게 풀 수 있다.

 

 구간이 1로만 구성되어있거나 -1로만 구성되어있다면 무조건 나누는 것이 이득이다.

그리고 구간의 합이 0인 구간은 p가 0이 되는데, 0이 아닌 구간은 모두 1혹은 -1로 p값이 1이 되므로, 0인 구간을 최대한 많이 만들었을 때가 최적이다.

 -1과 1의 개수가 같다면 전체를 한 구간으로 했을 때 p의 합이 0이므로 0이 정답이다. 1이 -1보다 많다면 그 많은 개수 만큼 1 하나짜리 구간을 만들고, 나머지를 모두 0으로 만들면 되고, -1이 더 많을 때는 반대로 하면 된다. 이렇게 하면 -1과 1의 개수 차이가 정답이 된다.

 

 이 문제에서는 구간을 어떻게 쪼개야 하는지는 묻지 않았지만, 만약 쪼개라고 했다면 스택을 하나 가지고 처음부터 끝까지 스위핑을 하면서 0이 되는 구간을 적절히 만들어주면 될 것 같다.

 

업솔빙

C. Grouping Increases

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
 
	int T;
	cin >> T;
 
	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;
 
		int res = 0;
		// always a is bigger or equal then b
		int a = 987654321, b = 987654321;
 
		for (int i = 0; i < n; i++) {
			int input;
			cin >> input;
 
			if (input <= b) {
				b = input;
			}
			else if (input <= a) {
				a = input;
			}
			else {
				res++;
				b = a;
				a = input;
			}
		}
 
		cout << res << '\n';
	}
 
	return 0;
}
 
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

C는 배열을 두개의 배열로 나누되, 증가하는 부분 개수를 가장 작게 나누었을 때 증가하는 부분의 개수가 몇개인지를 구하는 최적화 문제이다. 처음에 봤을때 백준의 경찰차 DP(https://www.acmicpc.net/problem/2618)가 떠올랐지만, n이 최대 200000이므로 O(n^2)풀이는 불가능하다. 여기서 한가지 아이디어를 얻을 수 있는데, 결국 두개의 배열에 대해 마지막 값 만이 다음 원소를 삽입할 때 증가하는 부분을 만드는지 그렇지 않은지를 결정하게 된다.

 

두 배열의 마지막 값을 각각 a, b (a >= b)라고 해보자. a와 b의 값은 클 수록 좋다.

c라는 값을 배열에 넣을 차례가 되었다고 하자.

 

1) c > a라면 c > b이기 때문에 무조건 증가하는 부분이 하나 생기게 되고, a에 넣을지 b에 넣을지를 결정해야 하는데, a, b가 클수록 좋으므로 b 뒤에 c를 넣는 것이 무조건 유리하다. (c, b) 보다 (c, a)가 더 좋기 때문이다.

 

2) c <= b라면 c <= a이고, 어디에 넣어도 증가하는 부분은 생기지 않기 때문에 b뒤에 c를 넣는 것이 이득이다. (a, c)가 (b, c)보다 더 좋기 때문이다.

 

3) b < c <= a라면 a를 낮추면서 증가하는 부분을 만들지 않거나, b를 높이면서 증가하는 부분을 하나 만들어야 하는데, 이때는 a를 낮추는 선택을 하는 것이 최선이다. 왜냐하면 b를 높여서 발생할 수 있는 최대의 이득은 증가하는 부분 하나를 줄이는 것인데, b를 높이면서 증가하는 부분이 이미 하나 늘었기 때문에 b를 높이지 않음으로 발생하는 손해는 없다.

 

1), 2), 3)의 관찰에 의해서 a, b값을 저장할 변수를 만들고 배열을 한번 스위핑하면 문제를 풀 수 있다. 초기 조건으로는 a, b를 모두 가능한 배열의 최대값보다 큰 값으로 설정해주면 된다. 3)번이 그리디한 관찰이었는데, 저 관찰을 하면 쉽게 풀리는 문제이다.