Codeforces Round #744 (Div. 3) , 1466 -> 1561 (+95)

Dashboard - Codeforces Round #744 (Div. 3) - Codeforces

Dashboard - Codeforces Round #744 (Div. 3) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. Casimir's String Solitaire

Problem - A - Codeforces

Problem - A - Codeforces

 

문제

 

string 이 테스트케이스에 맞게 1개씩 출력된다. 'A' , 'B' , 'C'로만 구성되어 있으며, 2개의 액션중 한번에 한가지를 통해 (여러번 할 수 있다) 모든 문자를 지울 수 있으면 YES 출력하면 되는 문제

1. A 와 B를 지운다.

2. B와 C를 지운다.

 

풀이

 

A와 B와 C의 카운트를 재서, CNT[A] + CNT[C] == CNT[B]이면 YES

 

코드

#include <bits/stdc++.h>
using namespace std;
int cnt[130];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		if (s.size() % 2) {
			cout << "NO\n";
			continue;
		}
		for (int i = 'A'; i <= 'C'; i++)cnt[i] = 0;
		for (int i = 0; i < s.size(); i++) {
			cnt[s[i]]++;
		}
		if (cnt['B'] == (cnt['A']+cnt['C']))cout << "YES\n";
		else cout << "NO\n";
	}
}

B. Shifting Sort

Problem - B - Codeforces

Problem - B - Codeforces

문제

 

N개의 수로 이루어진 배열이 주어진다. 이때 L..R 구간을 정하고 왼쪽으로 임의의 수(0 ~ N)만큼 시프트를 할 수 있다. 이때 정렬을 하기 위한 시프트 수와 어디 구간을 시프트 했는지 출력할 것

 

풀이

 

i = 1 ... N-1까지 , i ~ N 의 최소 숫자를 찾아 i로 왼쪽 시프트를 시켜주고 , 그대로 시프트를 구현한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int a[51], b[51];
void leftGo(int x, int y, int d) {
	for (int i = x; i <= y; i++) {
		int idx = i - d;
		if (idx < x) {
			int dif = idx - x + 1;
			idx = y + dif;
			b[idx] = a[i];
		}
		else {
			b[idx] = a[i];
		}
	}
	for (int i = x; i <= y; i++)a[i] = b[i];
}
struct A {
	int x, y, d;
};
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)cin >> a[i];
		int ans = 1;
		vector<A> ansV;
		while (ans<n) {
			int MIN = 1000000001, idx = 0;
			for (int i = ans; i <= n; i++) {
				if (MIN > a[i]) {
					MIN = a[i];
					idx = i;
				}
			}
			int dif = idx - ans;
			if (dif == 0) {
				ans++; continue;
			}
			ansV.push_back({ ans,idx,dif });
			leftGo(ans, idx, dif);
			ans++;
		}
		cout << ansV.size() << '\n';
		for (A k : ansV) {
			cout << k.x << ' ' << k.y << ' ' << k.d << '\n';
		}
	}
}

 

C. Ticks

Problem - C - Codeforces

Problem - C - Codeforces

문제

 

가장 아래 셀에서 부터 시작해, 자신의 윗칸 +i , -i 열의 셀만큼 색칠 할때 , 최소 i 가 주어지고 이 조건에 맞게 배열이 주어졌는지 확인하는 문제

 

풀이

 

가장 오른쪽 아래로 부터 최소 i 에 적합하면 체크해주고, 모든 셀이 체크가 됐으면 YES를 출력해주면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
string s[20];
bool check[20][20];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		bool flag = true;
		int n, m, k;
		cin >> n >> m >> k;
		for (int i = 0; i < n; i++)cin >> s[i];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				check[i][j] = false;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				if (s[i][j] == '.') {
					check[i][j] = true;
					continue;
				}
				if (s[i][j] == '*') {
					int cnt = 1;
					while (true) {
						//인덱스 검사
						int i2 = i - cnt;
						if (i2 < 0)break;
						int j2 = j - cnt;
						if (j2 < 0)break;
						int j3 = j + cnt;
						if (j3 >= m)break;
						//* 검사
						if (s[i2][j2] != '*')break;
						if (s[i2][j3] != '*')break;
						cnt++;
					}
					cnt--;
					if (cnt < k) {
						if (check[i][j])continue;
						else {
							flag = false;
							break;
						}
					}
					else {
						check[i][j] = true;
						cnt = 1;
						while (true) {
							//인덱스 검사
							int i2 = i - cnt;
							if (i2 < 0)break;
							int j2 = j - cnt;
							if (j2 < 0)break;
							int j3 = j + cnt;
							if (j3 >= m)break;
							//* 검사
							if (s[i2][j2] != '*')break;
							if (s[i2][j3] != '*')break;
							check[i2][j2] = check[i2][j3] = true;
							cnt++;
						}
					}
				}
			}
			if (flag == false)break;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (check[i][j] == false) {
					flag = false;
					break;
				}
			}
			if (flag == false)break;
		}
		if (flag)cout << "YES\n";
		else cout << "NO\n";
	}
}

D. Productive Meeting

Problem - D - Codeforces

Problem - D - Codeforces

문제

 

n개의 수가 주어진다. 이 때 1 이상의 숫자 2개를 선택해 1씩 뺀다. 이때 가능한 최대 횟수와 조합을 출력하는 문제

 

풀이

 

Max-Heap 에 1이상의 모든 수를 넣고 2개씩 빼서 그대로 구현

 

코드

#include <bits/stdc++.h>
using namespace std;
struct A {
	int x, y;
	bool operator<(const A& p)const {
		return y < p.y;
	}
};
priority_queue<A> pq;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<pair<int, int>> ans;
		for (int i = 1; i <= n; i++) {
			int t;
			cin >> t;
			if (t > 0)pq.push({ i,t });
		}
		int size = pq.size();
		while (true) {
			if (size < 2)break;
			A a1 = pq.top(); pq.pop();
			A a2 = pq.top(); pq.pop();
			size -= 2;
			ans.push_back({ a1.x,a2.x });
			a1.y--; a2.y--;
			if (a1.y > 0) {
				pq.push(a1);
				size++;
			}
			if (a2.y > 0) {
				pq.push(a2);
				size++;
			}
		}
		while (!pq.empty())pq.pop();
		cout << ans.size() << '\n';
		for (pair<int, int> kk : ans) {
			cout << kk.first << ' ' << kk.second << '\n';
		}
	}
}

E1. Permutation Minimization by Deque

Problem - E1 - Codeforces

Problem - E1 - Codeforces

문제

 

n 개의 수가 주어졌을 때, 덱에다가 순서대로 넣는다. 이때 최소로 작은 배열을 만드는 문제

 

풀이

 

덱에 Front와 넣을 수를 비교하여 , 넣을 수가 더 크면 뒤에 배치, 더 작으면 앞에 배치하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
deque<int> deq;
int a[200001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)cin >> a[i];
		deq.push_front(a[1]);
		for (int i = 2; i <= n; i++) {
			if (deq.front() > a[i])deq.push_front(a[i]);
			else deq.push_back(a[i]);
		}
		while (!deq.empty()) {
			cout << deq.front()<<' ';
			deq.pop_front();
		}
		cout << '\n';
	}
}

 

E2. Array Optimization by Deque

Problem - E2 - Codeforces

Problem - E2 - Codeforces

문제

 

n개의 수를 임의로 덱에 넣는데, inversion의 최소 값을 출력하는 문제

 

풀이

 

n개의 수를 좌표압축하고, 덱에 들어간 수들 중 i번쨰 수보다 작은 값, 큰 값을 비교해 더 작은것을 더해주고 i번째 수를 갱신시켜 준다. 이때 작은 값 큰값을 비교할때는 세그먼트 트리를 이용

 

코드

#include <bits/stdc++.h>
using namespace std;
long long a[200001], d[800001];
void init(int node, int start, int end) {
	if (start == end) {
		d[node] = 0;
		return;
	}
	int mid = (start + end) / 2;
	init(node * 2, start, mid);
	init(node * 2 + 1, mid + 1, end);
	d[node] = 0;
}
void Update(int node, int start, int end, int i) {
	if (start > i || end < i)return;
	d[node]++;
	if (start == end)return;
	int mid = (start + end) / 2;
	Update(node * 2, start, mid, i);
	Update(node * 2 + 1, mid + 1, end, i);
}
long long query(int node, int start, int end, int i, int j) {
	if (start > j || end < i)return 0;
	if (start >= i && end <= j)return d[node];
	int mid = (start + end) / 2;
	return query(node * 2, start, mid, i, j) + query(node * 2 + 1, mid + 1, end, i, j);
}
struct A {
	long long idx, num;
	bool operator<(const A& p)const {
		return num < p.num;
	}
};
A b[200001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			b[i].idx = i;
			b[i].num = a[i];
		}
		if (n == 1) {
			cout << "0\n";
			continue;
		}
		sort(b + 1, b + 1 + n);
		long long start = 1;
		a[b[1].idx] = start;
		for (int i = 2; i <= n; i++) {
			if (b[i].num == b[i - 1].num) {
				a[b[i].idx] = start;
			}
			else {
				start++;
				a[b[i].idx] = start;
			}
		}
 
		init(1, 1,start);
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			long long MIN, MAX;
			if (a[i] == 1)MIN = 0;
			else {
				MIN = query(1, 1, start, 1, a[i] - 1);
			}
			if (a[i] == start) {
				MAX = 0;
			}
			else {
				MAX = query(1, 1, start, a[i] + 1, start);
			}
			ans += min(MIN, MAX);
			Update(1, 1, start, a[i]);
		}
		cout << ans;
		cout << '\n';
	}
}

 

 

레이팅 변화 : 

1466 -> 1561 (+95)

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.