[CF] Round #691 (Div. 2) _ 201219

(2020년 12월 20일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #691 (Div. 2) - Codeforces

 

A.

카드 중에서 R > B인거, R < B인거의 개수를 센 다음

R > B인것의 개수가 더 많으면 RED,

R < B인게 더 많으면 BLUE,

같으면 EQUAL

 

어차피 뽑힐 확률은 모두 동일하기 때문에

개수로 판단해도 된다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int cntR, cntB;
	int i;

	cin >> T;
	while (T--) {
		cin >> N;
		vector<char> R(N + 5), B(N+5);
		for (i = 0; i < N; i++) {
			cin >> R[i];
		}
		for (i = 0; i < N; i++) {
			cin >> B[i];
		}
		
		cntR = cntB = 0;
		for (i = 0; i < N; i++) {
			if (R[i] > B[i]) {
				cntR++;
			}
			else if (R[i] < B[i]) {
				cntB++;
			}
		}

		if (cntR > cntB) {
			cout << "RED" << '\n';
		}
		else if (cntR < cntB) {
			cout << "BLUE" << '\n';
		}
		else {
			cout << "EQUAL" << '\n';
		}
	}

	return 0;
}

​

B.

처음에 문제를 이해하는 데 시간이 좀 걸렸다...

그래서 좀 더 빨리 못 푼게아쉽다...ㅠㅠ

​

그리고 이 문제가 생각보다 쉬운건데 시간이 많이 걸렸다...

그림을 조금 그려보니까

규칙이 보여서 그냥 그걸 구현했더니 맞았다.

그래서 코드도 엄청 짧다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	int i;

	cin >> N;
	if (N % 2 == 0) {
		cout << (N / 2 + 1) * (N / 2 + 1) << '\n';
	}
	else {
		cout << 2 * (N / 2 + 1) * (N / 2 + 2) << '\n';
	}

	return 0;
}

​​

C.

아쉽다..

 

O(NM)은 절대 불가능이다.

근데 각 경우에서 더해주는 값이 모두 같다는 데 집중해보면...

수들간의 간격은, 더해지는 수와 상관없이 항상 동일하다.

그렇기 때문에 그 간격은 gcd의 배수여야 한다.

​

그래서 그 간격들에 대한 gcd를 구하고, (변수 이름을 gcd_all이라 하면)

더해지는 값이 들어올 때

GCD((가장 작은 수 + 더해지는 값), gcd_all)

이게 답이다...

​

근데 이걸 결국 틀린 이유는

배열 a에 중복된 원소가 있을 수 있다는 생각을 전혀 못했다..ㅠㅠ

아쉽다

using ll = long long;
ll GCD(ll k, ll l) { return l ? GCD(l, k % l) : k; }

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M;
	ll gcd_all;
	ll add;
	int i;

	cin >> N >> M;
	vector<ll> A(N + 5);
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.begin() + N);
	A.erase(unique(A.begin(), A.begin() + N), A.end());

	if (A.size() == 1) {
		for (i = 0; i < M; i++) {
			cin >> add;
			cout << A[0] + add << ' ';
		}
		return 0;
	}

	gcd_all = A[1] - A[0];
	for (i = 2; i < A.size(); i++) {
		gcd_all = GCD(gcd_all, A[i] - A[i - 1]);
	}

	for (i = 0; i < M; i++) {
		cin >> add;
		cout << GCD(gcd_all, A[0] + add) << ' ';
	}

	return 0;
}