Codeforces Round #462 (Div. 2)

* Codeforces Round #462 (Div. 2)

A. A Compatible Pair

  곱셈에 대해 가장 작게 만들기 위해 for문을 세 개로 구성해서 Brute force로 알아낼 수 있다.

  O(N^2 M)

#include <iostream>
using namespace std;
using ll = long long;
ll min_v(ll a, ll b) { return a < b ? a : b; }
ll max_v(ll a, ll b) { return a > b ? a : b; }
int main() {
	int n, m,i,j,k;
	ll ans=1e18, tmp, A[50], B[50];
	cin >> n >> m;
	for (i = 0; i < n; i++) cin >> A[i];
	for (i = 0; i < m; i++) cin >> B[i];

	for (i = 0; i < n; i++) {
		tmp = -1e18;
		for (j = 0; j < n; j++) {
			if (i == j) continue;
			for (k = 0; k < m; k++)
				tmp = max_v(tmp, A[j] * B[k]);
		}
		ans = min_v(ans, tmp);
	}
	cout << ans;
	return 0;
}

B. A Prosperous Lot

  숫자 안에 갇힌 공간의 수를 세는 프로그램이다. 1e18을 넘어선 안되는 점을 감안하고, 0이 맨 앞에 없다는 것을 생각한다면 8과 6,4로 충분히 구현할 수 있음을 알 수 있다.

#include <iostream>
using namespace std;
using ll = long long;
int main() {
	int k,pos=0;
	ll n = 0;
	cin >> k;
	while (pos < 18 && k) {
		n *= 10;
		if (k == 1) n += 6, k--;
		else n += 8, k -= 2;
		pos++;
	}
	cout << (k ? -1 : n);
	return 0;
}

C. A Twisty Movement

  부분 수열과 특정 증명 방법을 통해 알 수 있다.

  부분 수열에 대해 1..2..1..2 형식일 때 중간 2..1을 뒤집을 때 최대가 되는 부분을 찾아야한다.

  1212 순서에 대해 먼저 각 part가 끝나는 경우에 대해서 처리해준다. 그 다음 각 part 다음 숫자에 대해 처리할 때 앞에서 처리한 것에 대해 dynamic하게 처리해준다.

시간 복잡도 : O(N)

#include <cstdio>
int max_v(int a, int b) { return a > b ? a : b; }
int main() {
	int n, i, j, *A, ans = 0, *up, *down, tmp, dp[5][2001] = {}, parts[5] = { 0,1,2,1,2 };
	scanf("%d", &n);
	A = new int[n + 1]{};
	for (i = 1; i <= n; i++)
		scanf("%d", &A[i]);
	for (i = 1; i < 5; i++) {
		for (j = 1; j <= n; j++)
			dp[i][j] = max_v(dp[i][j - 1] + (parts[i] == A[j]), dp[i - 1][j]);
	}
	printf("%d", dp[4][n]);
	return 0;
}

D. A Determined Cleanup

E. A Colourful Prospect