Algorithm/코드포스

Codeforces Round #743 (Div. 2) , Unrated

Edyy 2021. 9. 19. 03:41

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

 

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

 

codeforces.com

 

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

 

A. Countdown

Problem - A - Codeforces

 

Problem - A - Codeforces

 

codeforces.com

 

문제

 

계산기에 숫자가 표시된다. 이 때

1. 1을 뺀다

2. 2개의 자리 수를 정해 위치를 바꾼다

한번의 연산에 하나씩 하면서, 최소 연산으로 0을 만들 때 최소 연산의 수를 출력하는 문제

 

풀이

 

각 자리수를 정답에 추가시키고, 각 자리수가 끝자리가 아니라면 정답을 1씩 더 추가시켜 준다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n,ans=0;
		string s;
		cin >> n >> s;
		for (int i = 0; i < n; i++) {
			if (s[i] != '0') {
				ans += (s[i] - '0');
				if (i != (n - 1))ans++;
			}
		}
		cout << ans << '\n';
	}
}

 

B. Swaps

Problem - B - Codeforces

 

Problem - B - Codeforces

 

codeforces.com

문제

 

1 ~ 2n 까지 a 배열에는 홀수만 , b 배열에는 짝수만 주어진다. 이때 각 배열에서 i를 선정하여

i와 i+1번째 숫자를 swap할 수 있다. 이때 a < b를 만들 수 있는 최소 swap의 수를 구하는 문제

 

풀이

 

D[i] = a배열에서 숫자 i이하의 모든 수중에서 최소 인덱스 

ans = min( ans, d[b[i]]+ idx[b[i]] ) 
정답은 b[i] 이하 숫자 최소인덱스 + b[i]의 인덱스 중 최솟 값을 출력하면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[100001], b[100001];
int aidx[200001], bidx[200001];
int d1[200001], d2[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 = 0; i < n; i++) {
			cin >> a[i];
			aidx[a[i]] = i;
		}
		for (int i = 0; i < n; i++) {
			cin >> b[i];
			bidx[b[i]] = i;
		}
		int n2 = n * 2;
		d1[1] = d1[2] = aidx[1];
		for (int i = 3; i <= n2;i+=2){
			d1[i] = min(d1[i - 1], aidx[i]);
			d1[i + 1] = d1[i];
		}
		int MAX = 0,start=0,ans=1000000;
		for (int i = 0; i < n; i++) {
			ans = min(ans, d1[b[i]]+bidx[b[i]]);
		}
		
		for (int i = 1; i <= n2; i++) {
			d1[i] = 0;
		}
		cout << ans << '\n';
	}
}

C. Book

Problem - C - Codeforces

 

Problem - C - Codeforces

 

codeforces.com

 

문제

 

n개의 챕터와 선행 챕터가 주어진다. 1부터 n까지 챕터를 쭉 공부하되, 선행 챕터를 공부 못했으면 못배우고 넘어간다.

이 때 쭉 반복해서 모두 배울 수 있다면 반복 횟수, 못배운다면 -1을 출력하는 문제

 

풀이

 

위상 정렬을 이용하여 풀되, 큐 2개를 이용하여 반복 횟수를 구한다. 이 때 못 배운 챕터가 있으면 -1 이고, 첫번째로 사용하는 큐는 min-heap을 사용해야한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
vector<int> v[200001];
int ind[200001];
priority_queue<int, vector<int>, greater<int>> pq;
queue<int> q2;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		while (!pq.empty())pq.pop();
		while (!q2.empty())q2.pop();
		int n,ans=0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			ind[i] = 0;
			v[i].clear();
		}
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			ind[i] += x;
			for (int j = 0; j < x; j++) {
				int t;
				cin >> t;
				v[t].push_back(i);
			}
		}
		for (int i = 1; i <= n; i++) {
			if (ind[i] == 0) {
				pq.push(i);
			}
		}
		while (!pq.empty()) {
			while (!pq.empty()) {
				int x = pq.top();
				pq.pop();
				for (auto k : v[x]) {
					ind[k]--;
					if (ind[k] == 0) {
						if (k > x)pq.push(k);
						else q2.push(k);
					}
				}
			}
			while (!q2.empty()) {
				pq.push(q2.front());
				q2.pop();
			}
			ans++;
		}
		bool flag = true;
		for (int i = 1; i <= n; i++) {
			if (ind[i]) {
				flag = false;
				break;
			}
		}
		if (flag)cout << ans << '\n';
		else cout << -1 << '\n';
	}
}

 

레이팅 변화 : 

중간에 채점 이슈로 인해 언레이팅 대회가 되었습니다.. 

점수는 그대로이며 아쉬운데로 퍼포먼스만 캡처했습니다.

 

 

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

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