Codeforces Round #684 (Div.2)

 

 

 

 

어제 있었던 Div.2 코드포스 라운드의 풀이이다. 총 3솔브를 했다.

 

A. Buy the String

 

이진 수열을 적당히 변환시켜 수열을 구매하는 값을 최소화시키는 문제이다.

0의 가격, 1의 가격, 변환 비용의 대소 비교를 통해 쉽게 문제를 해결할 수 있다.

 

시간 복잡도는 $O(N)$이다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {

		long long n, c0, c1, h;
		string s;
		cin >> n >> c0 >> c1 >> h;
		cin >> s;
		long long cost = 0;
		if (c0 >= c1) {
			if (h < c0 - c1) {
				for (int i = 0; i < n; i++) {
					if (s[i] == '0') {
						cost += h;
						s[i] = '1';
					}
				}
			}
		}
		if (c0 < c1) {
			if (h < c1 - c0) {
				for (int i = 0; i < n; i++) {
					if (s[i] == '1') {
						cost += h;
						s[i] = '0';
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (s[i] == '0')cost += c0;
			else cost += c1;
		}
		cout << cost << '\n';
	}
}

 

B. Sum of Medians

 

문제에서 중앙값의 정의를 주고, $N \times K$개의 원소를 가진 수열을 주고, 해당 수열을 $K$개의 원소를 가진 $N$개의 수열로 나누어 각 수열의 중앙값의 합을 최대화시키는 문제이다.

 

예제를 잘 분석하면, 해당 수열에서 첫째항이 $K \times \lfloor \frac{N-1}{2} \rfloor $ 이고, 공차가 $N - \lfloor \frac{N-1}{2} \rfloor $인 등차수열의 합이 답이 됨을 알 수 있다.

 

시간 복잡도는 $O(NK)$이다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {

		int N, K; cin >> N >> K;

		vector<long long> v(N*K);
		for (int i = 0; i < N*K; i++)cin >> v[i];
		long long res = 0;
		for (int k = K*((N - 1) / 2); k < N*K; k += N - (N - 1) / 2) {
			res += v[k];
		}
		cout << res << '\n';
	}
}

 

 

C1. Binary Table (Easy Version)

 

정말 구현이 어려웠던 문제이다. Easy Version은 사용할 수 있는 연산의 횟수가 많아서 naive하게 매 4칸마다 전부 0으로 만들며 내려와도 된다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {
		int N, M; cin >> N >> M;
		bool arr[101][101] = { 0 };
		vector<tuple<int, int, int, int, int, int>>ans;
		for (int i = 0; i < N; i++) {
			string in; cin >> in;
			for (int j = 0; j < M; j++) {
				arr[i][j] = in[j] - '0';
			}
		}
		auto p = [&](int a1, int a2, int a3, int a4, int a5, int a6) {
			ans.push_back({ a1,a2,a3,a4,a5,a6 });
		};
		auto f = [&](int x, int y) {
			arr[x][y] = arr[x + 1][y] = arr[x][y + 1] = arr[x + 1][y + 1] = 0;
		};
		auto fix = [&](int x, int y)->void {
			int p1 = arr[x][y];
			int p2 = arr[x][y + 1];
			int p3 = arr[x + 1][y];
			int p4 = arr[x + 1][y + 1];
			if (p1 == 0) {
				if (p2 == 0) {
					if (p3 == 0) {
						if (p4 == 0) {//00 00
						}
						else {
							//00 01
							p(x, y, x + 1, y, x + 1, y + 1);
							p(x, y, x, y + 1, x + 1, y + 1);
							p(x, y + 1, x + 1, y + 1, x + 1, y);
							f(x,y);
						}
					}
					else {
						if (p4 == 0) {//00 10
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x + 1, y, x + 1, y + 1);
							p(x + 1, y, x + 1, y + 1, x, y + 1);
							f(x, y);
						}
						else {//00 11
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x, y + 1, x + 1, y + 1);
							f(x, y);
						}

					}
				}
				else {
					if (p3 == 0) {
						if (p4 == 0) {//01 00
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x, y + 1, x + 1, y + 1);
							p(x + 1, y, x + 1, y + 1, x, y + 1);
							f(x, y);
						}
						else {
							//01 01
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x + 1, y, x + 1, y + 1);
							f(x, y);
						}
					}
					else {
						if (p4 == 0) {//01 10
							p(x, y, x + 1, y, x + 1, y + 1);
							p(x, y, x, y + 1, x + 1, y + 1);
							f(x, y);
						}
						else {//01 11
							p(x, y + 1, x + 1, y, x + 1, y + 1);
							f(x, y);
						}

					}
				}
			}
			else {
				if (p2 == 0) {
					if (p3 == 0) {
						if (p4 == 0) {//10 00
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x + 1, y, x + 1, y + 1);
							p(x, y, x, y + 1, x + 1, y + 1);
							f(x, y);
						}
						else {
							//10 01
							p(x, y, x + 1, y, x, y + 1);
							p(x + 1, y + 1, x, y + 1, x + 1, y);
							f(x, y);
						}
					}
					else {
						if (p4 == 0) {//10 10
							p(x, y, x, y + 1, x + 1, y + 1);
							p(x + 1, y, x + 1, y + 1, x, y + 1);
							f(x, y);
						}
						else {//10 11
							p(x, y, x + 1, y, x + 1, y + 1);
							f(x, y);
						}

					}
				}
				else {
					if (p3 == 0) {
						if (p4 == 0) {//11 00
							p(x, y, x + 1, y, x + 1, y + 1);
							p(x + 1, y, x + 1, y + 1, x, y + 1);
							f(x, y);
						}
						else {//11 01
							p(x, y, x, y + 1, x + 1, y + 1);
							f(x, y);
						}
					}
					else {
						if (p4 == 0) {//11 10
							p(x, y, x, y + 1, x + 1, y);
							f(x, y);
						}
						else {//11 11
							p(x, y, x, y + 1, x + 1, y + 1);
							p(x + 1, y, x + 1, y + 1, x, y + 1);
							p(x, y, x + 1, y, x, y + 1);
							p(x, y, x + 1, y, x + 1, y + 1);
							f(x, y);
						}

					}
				}
			}
		};
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j < M - 1; j++) {
				fix(i, j);
			}
		}
		cout << ans.size() << '\n';
		for (int i = 0; i < ans.size(); i++) {
			int a1, a2, a3, a4, a5, a6;
			tie(a1, a2, a3, a4, a5, a6) = ans[i];
			cout << a1 + 1 << ' ' << a2 + 1 << ' ' << a3 + 1 << ' ' << a4 + 1 << ' ' << a5 + 1 << ' ' << a6 + 1 << '\n';
		}
	}
}