[CF] Round #556 (Div. 2) _ 210124

(2021년 1월 25일에 작성한 글입니다.)

 

Standings - Codeforces Round #556 (Div. 2) - Codeforces

학회 코포 스터디에서 버추얼로 풀었다.

​

A.

A가 A 같지가 않았다

문제 이해하는데 꽤 시간 걸렸지만 그래도 구현은 쉬웠다.

구매 가격 중 가장 낮은거, 판매 가격 중 가장 높은 걸 비교해서

만약 더 비싸게 팔 수 없으면 아무 처리도 하지 않고,

더 비싸게 팔 수 있다면 최대한 구매한 뒤 되팔면 된다.​

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

	cin >> N >> M >> K;
	vector<ll> buy(N), sell(M);
	for (int i = 0; i < N; i++) {
		cin >> buy[i];
	}
	sort(buy.begin(), buy.end());
	for (int i = 0; i < M; i++) {
		cin >> sell[i];
	}
	sort(sell.begin(), sell.end(), greater<>());

	ll stock = 0;
	if (buy[0] < sell[0]) {
		stock += K / buy[0];
		K %= buy[0];
		K += stock * sell[0];
	}

	cout << K << ENDL;

	return 0;
}

​

B.

ㅋㅋㅋㅋA번에서 약간 당황하고 B번 보니까 더 당황스러웠다.

처음에는 N이 작으니까 모든 빈칸에 대해 BFS를 돌려야 되는 줄 알았다

근데 빠르게 늘어나는 ac들을 보면서 그건 아니라는 걸 느꼈고

그냥 왼쪽 위부터 확인하면서 만약 빈칸이 있으면

그게 십자가의 위쪽 부분이 되어야 한다 무조건.

그렇게 처리 해서 만약 타일을 다 채울 수 있으면 YES

아니면 NO

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

	cin >> N;
	vector<vector<char>> arr(N + 5, vector<char>(N + 5));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			arr[i][j] = arr[i][j] == '.' ? 1 : 0;
		}
	}

	bool ans = true;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j]) {
				if (arr[i + 1][j - 1] && arr[i + 1][j] && arr[i + 1][j + 1] && arr[i + 2][j]) {
					arr[i][j] = 0;
					arr[i + 1][j - 1] = 0;
					arr[i + 1][j] = 0;
					arr[i + 1][j + 1] = 0;
					arr[i + 2][j] = 0;
				}
				else {
					ans = false;
					break;
				}
			}
		}
	}

	if (ans) {
		cout << "YES" << ENDL;
	}
	else {
		cout << "NO" << ENDL;
	}
	return 0;
}

​​

C.

이거 진짜 재밌는 문제였다

인접한 소수들 간의 차는 2->3을 제외하면 모두 2의 배수이다

2를 제외한 소수들은 모두 홀수니까!

우왕...

그래서 앞에 prefix가 2->3이 되도록 만들어주고,

그 후에는 2를 모두 출력하고, 1을 모두 출력하면 된다.

​

시작은 수열을 {2, 1, ...}로 시작해야 한다.

그래야 prefix가 2, 3, .. 이렇게 나오니까.

​​

근데...ㅋㅋㅋㅋ

지금 보니까 엄청 돌아갔네...

처음에는 1의 개수가 홀수일 때 / 짝수일 때를 나눠서

1이 짝수개면 시작이 1 1 2 1 ..

홀수개이면 2 1 2 ... 1 ... 이렇게 되야 한다고 생각했는데

아니어서 케이스를 안 나눴다.

그리고 결국 ac받은 코드는

소수들을 구해놓고 인접한 소수 간의 차이를 계산해서

2 한번 or 1 두 번 출력할때마다 그 차이에서 빼준 방식이다..

​

왜 그랬지?? 그럴 필요가 전혀 없다

그냥 2, 1, 2, ..., 1, ...

이런식으로 출력하면 된다

vector<int> primeNums;
vector<bool> isPrime;
void era(ll MAX)
{
	isPrime.resize(MAX + 1, true);
	ll i, j;

	isPrime[0] = isPrime[1] = false;

	for (i = 2; i <= MAX; i++) {
		if (isPrime[i]) {
			primeNums.push_back(i);
			for (j = i * i; j <= MAX; j += i) {
				isPrime[j] = false;
			}
		}
	}
}

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

	cin >> N;
	int cnt[3] = {0};
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		cnt[a]++;
	}

	if (cnt[1] == N) {
		for (int i = 0; i < N; i++) {
			cout << 1 << ' ';
		}
		return 0;
	}
	if (cnt[2] == N) {
		for (int i = 0; i < N; i++) {
			cout << 2 << ' ';
		}
		return 0;
	}

	cnt[2]--;
	cout << 2 << ' ';
	cnt[1]--;
	cout << 1 << ' ';

	for (int i = 2; ; i++) {
		int diff = primeNums[i] - primeNums[i - 1];
		while (diff && cnt[2]) {
			cnt[2]--;
			diff -= 2;
			cout << 2 << ' ';
		}
		while (diff && cnt[1] >= 2) {
			cnt[1] -= 2;
			diff -= 2;
			cout << 1 << ' ' << 1 << ' ';
		}

		if (cnt[2] == 0 && cnt[1] <= 1) {
			if (cnt[1]) {
				cout << 1 << ' ';
			}
			break;
		}
	}

	return 0;
}