배치 여섯째 판

대회 요약

스코어보드

 배치 마지막 판은 Div2 라운드였다. 기본 점수 50점을 주기 때문에 이번에 무난하게 하면 블루를 달성할 것이라 생각했지만, 역시 모든 일이 생각처럼 풀리지는 않는 것 같다.

 A는 A치고 어려웠던 것 같고, 그래도 단순 구현 문제라서 하라는대로 구현하고 AC를 받았다. B는 전형적인 정렬 후 그리디와 스위핑이었고, 생각하면서 구현하고 한번에 맞췄다.

 C에서부터 문제가 생겼다. 배열을 나눌 수 있는 크기가 적기 때문에, 모든 나누는 경우에 대해서 검증을 하면 된다는 것 까지는 알았다. 그리고 조건을 만족하는지 확인하는 부분을, 에테체로 모든 소수를 구해놓고 확인해봤다. 숫자가 작아서 될 줄 알았지만, TLE를 받고, 몇번 커팅을 시도하다가 계속 TLE만 받고 넘어갔다. D는 2번연산을 많아야 60번 할 수 있다는 것을 이용해서 잘 구현하면 될 것 같았지만, 구현을 시간 안에 못할 것 같아서 일단 넘어갔다. E의 제한을 보니 N^2 DP로 잘 하면 될 것 같았지만, 이미 대회가 끝나기 직전이라 대충 짜서 내고 TLE를 받고 결국 2솔로 대회를 마무리했다.

 

 순위는 4000등 정도를 하고 그린 급 퍼포먼스로 +7점(기본점수 50점을 생각하면 -43점)이 되었다.

 

 나중에 C를 업솔빙해보니 GCD로 잘 하면 금방 풀리는 문제였는데, 정수론 문제는 확실히 정수론으로 접근해야겠다는 생각을 했다.

 

A. Satisfying Constraints

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int table[100];

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 low = 0, up = 1987654321;
		int c = 0;
		for (int i = 0; i < n; i++) {
			int a, x;
			cin >> a >> x;

			if (a == 1) {
				low = max(low, x);
			}
			else if (a == 2) {
				up = min(up, x);
			}
			else {
				table[c] = x;
				c++;
			}
		}

		int cnt = up - low + 1;
		if (cnt <= 0) {
			cout << 0 << '\n';
			continue;
		}

		for (int j = 0; j < c; j++) {
			if (table[j] >= low && table[j] <= up) {
				cnt--;
			}
		}
		cout << cnt << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

A는 3가지의 제한이 n개 주어졌을때, 그 제한들을 모두 만족하는 정수의 개수를 구하는 문제였다.

 1번과 2번 제한은 하한과 상한을 제한하기 때문에, 각각의 최대와 최소 하나씩만 남기면 된다. 3번 조건이 문제인데, 1번과 2번 제한의 범위에 따라서 그 내부에 값이 있으면 결과에서 -1을 하고, 아니면 영향이 없다. 그런데 1번과 2번 제한이 여러개 들어오면서 변할 수 있으므로, 3번 제한은 모두 저장해두고 모든 제한이 입력돼서 1번과 2번 제한이 확정된 후에 처리하면 된다.

 3번 제한을 일종의 오프라인 쿼리로 처리한 것인데, 만약 제한이 입력되고 있는 중간에 현재 제한을 만족하는 수의 개수를 출력하는 쿼리가 있었다면 (온라인 쿼리로 처리해야 하면) 세그멘트 트리를 이용해서 구간에 있는 3번 쿼리의 개수를 세면 풀릴 것 같다.

 

B. Summation Game

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int table[200000];

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n, k, x;
		cin >> n >> k >> x;

		int curr = 0;
		for (int i = 0; i < n; i++) {
			cin >> table[i];
			table[i] *= -1;
			curr -= table[i];
		}
		sort(&table[0], &table[n]);

		int px;
		for (px = 0; px < x; px++) {
			curr += table[px] * 2;
		}

		int res = curr;
		for (int i = 0; i < k; i++) {
			curr -= table[i];
			if (px < n) {
				curr += table[px] * 2;
				px++;
			}
			res = max(res, curr);
		}

		cout << res << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

B는 게임이론 문제였는데, 주어진 배열에서 Alice가 몇개 이하의 원소를 지우고, Bob이 몇개 이하의 원소에 -1을 곱하는 연산을 했을 때, 결과를 구하는 문제이다.

 

 Bob은 배열의 합을 최대한 작게 만들고 싶어한다. 그러므로 Alice가 지우고 난 후의 배열에서 최대한 큰 원소부터 최대한 많이 -1을 곱하면 된다. x개 이하의 원소에 -1을 곱할 수 있지만, 배열의 모든 원소가 양수이기 때문에 x개 이상의 원소가 남아있을 때 x개 미만으로 곱할 필요가 없다.

 Bob이 어떻게 게임을 진행할 지가 확정되었으므로, Alice에 대해서는 그냥 모든 경우를 시도해볼 수가 있다. Bob이 큰 원소부터 -1을 곱하므로, Alice가 Bob을 방해하려면 큰 원소부터 지워야 한다. 그러므로 Alice가 큰 원소부터 0개~k개를 지우고, 각각에 Bob의 연산이 적용된 결과 중 최대값을 찾으면 그것이 답이다.

 

Alice의 연산과 Bob의 연산을 나이브하게 구현하면, k의 최대값이 n이고, 각각에 대해 x의 최대값이 n이므로 O(N^2)이 된다. n이 최대 20만이므로 이 구현은 TLE를 받는다.

Alice가 i개를 지웠을 때 결과를 R(i)라고 하자. R(i+1)은 i+1번째로 큰 원소를 지운 것이고, Bob은 그 원소에 * -1을 못 하게 되므로 현재 -1을 곱하지 않은 원소가 있다면 그 중 가장 큰 원소에 -1을 곱하게 된다. 그러므로 R(i+1)는 R(i)를 바탕으로 O(1)시간에 구할 수 있고, 이렇게 이전 결과를 바탕으로 결과값을 계속 계산하면 O(N)시간에 풀 수 있다.

 

업솔빙

C. Partitioning the Array

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

/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int inputs[200000];

int GCD(int a, int b) {
	if (b == 0) {
		return a;
	}

	return GCD(b, a % b);
}

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;

		for (int i = 0; i < n; i++) {
			cin >> inputs[i];
		}

		int res = 1;

		for (int d = 1; d <= n / 2; d++) {
			if (n % d != 0) {
				continue;
			}

			int curr = 0;
			for (int k = 1; k < n / d; k++) {
				for (int i = 0; i < d; i++) {
					int a = inputs[i], b = inputs[i + k * d];

					if (curr == 0) {
						curr = abs(a - b);
					}
					else {
						curr = GCD(curr, abs(a - b));
					}
				}
			}

			if (curr != 1) {
				res++;
			}
		}

		cout << res << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

C는 주어진 배열을 조건에 맞게 나누는 경우의 수가 몇개인지 확인하는 문제였다.

조건은 어떤 소수 m에 대해서, 각 배열의 값을 m에 대한 모듈러로 바꿨을 때 모든 배열이 동일해지는 소수 m이 존재하는 것이었다.

 

배열을 나누는 경우 자체가 배열의 약수의 개수만큼만 있고, 입력 제한 자체도 널널해서 에태체로 소수를 전부(약 19000개) 구해놓고 모든 m에 대해 시도해보는 코드를 짰다. TLE를 받았고 커팅을 해야 하나보다 하며 d개로 나눌 수 있다면 d*c개로도 나눌 수 있으므로 나누는데 성공한 경우를 기록해놓는 방법도 써봤지만, 여전히 TLE였다. 나중에 생각해보니 애초에 10000개의 테스트케이스가 주어지고 각각의 테스트케이스에서 길이 30의 배열이 주어지기만 해도 무조건 TLE였다.

 

대회가 끝나고 무식한 풀이를 버리고, 정수론 쪽으로 접근해보았다. m에 대한 모듈러 합동인 a1과 a2는 a2 = a1 + m * d (d는 정수)로 표현할 수 있다.

j개의 배열에 대해 확인을 한다면, 각 배열의 i번째 값 Aij에 대해, 모든 k에 대해 Akj = A1j + m * d로 나타낼 수 있다. 그러므로 모든 Akj - A1j에 대한 GCD m을 구하면 그 m은 조건을 만족시킨다.

배열을 d개로 나눈다면 각 부분배열의 크기는 N / d이고, GCD를 해야하는 횟수는 N / d * d = N이 된다.

그러므로 시간복잡도는 O(N * N의 약수의 개수)이고, N의 약수의 개수는 충분히 작으므로 그렇게 하면 맞는다.

 

PS에서 수학 문제 연습을 등한시 하다보니 모듈러 관련된 문제를 만나도 일단 컴퓨터적으로 해결하려는 성향이 있는것 같다. 모듈러 관련 문제는 (귀찮더라도) 먼저 정수론적으로 문제를 충분히 잘 모델링하고 풀어야 할 것같다.