Codeforces Round #753 (Div. 3) , 1457 -> 1567

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

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

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

 

 

A. Linear Keyboard

Problem - A - Codeforces

Problem - A - Codeforces

문제

a~z 까지 각 위치가 주어지고, string s를 입력할 때 각 인덱스의 차의 합을 출력하는 문제

 

풀이

 

인덱스 배열에 위치를 저장하고 나머지는 문제 그대로 구현한다

 

코드

 

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

B. Odd Grasshopper

 

Problem - B - Codeforces

Problem - B - Codeforces

문제

x와 n이 주어졌을 때 x에 1부터 n까지 x에 수를 더하거나 뺀다. 현재 x 값이 홀수라면 값을 더하고 짝수라면 값을 뺀다.

이때 n번째 연산까지 다 했을때의 값을 출력하는 문제

 

풀이

 

x가 홀수든 짝수든 4번만 하면 원래의 값으로 돌아온다. 고로 4로 나눈 나머지만 계산해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int idx[130];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		long long x, n;
		cin >> x >> n;
		long long div = (n / 4)*4;
		for (long long i = div + 1; i <= n; i++) {
			if (x % 2)x += i;
			else x -= i;
		}
		cout << x << '\n';
	}
}

C. Minimum Extraction

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

배열에서 가장 작은 값을 골라서 모든 나머지 원소에 빼고 , 가장 작은 값은 배열에서 제외시킨다. 이 때 임의로 이 동작을 반복할 수 있을때 남은 배열중에서 최소 값이 , 모든 연산 배열 중에서 최대값을 가지는 최소값을 출력하는 문제

 

풀이

 

최소 값을 가장 작은 수부터 빼면서 sum값을 이용하여 계산하고 이중에서 MAX값을 출력한다. 배열 중에서 어떤 값을 빼더라도 크기 순서는 바뀌지 않기 때문이다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
priority_queue<long long, vector<long long>, greater<long long>> 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;
		long long ans = -1000000001,sum=0;
		for (int i = 0; i< n; i++) {
			long long t;
			cin >> t;
			pq.push(t);
		}
		ans = max(ans,pq.top());
		int size = n;
		while (size != 1) {
			long long x = pq.top();
			pq.pop();
			size--;
			x += sum;
			ans = max(ans, x);
			sum -= x;
		}
		ans = max(ans, pq.top()+sum);
		pq.pop();
		cout << ans << '\n';
	}
}

D. Blue-Red Permutation

Problem - D - Codeforces

Problem - D - Codeforces

 

문제

n개의 수가 주어지고 각 수마다 파란색 혹은 빨간색으로 색칠되어있다. 이 때 파란색 수를 골라 -1씩, 빨간색 수를 골라 +1식 원하는 만큼 하고 최종적으로 permutation을 만들 수 있는지 판별하는 문제

 

풀이

 

1~n까지 숫자를 만드는데 , 순서는 파란색 가장 작은순서 -> 파란색 가장 큰 순서 - > 빨간색 가장 작은순서 -> 빨간색 큰 순서로 해야 가장 최선이기 때문에 이 순서대로 값을 찾고 모든 되는 값이 없으면 NO를 출력한다

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[200001];
string s;
vector<int> Blue, Red;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		Blue.clear();
		Red.clear();
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)cin >> a[i];
		cin >> s;
		for (int i = 0; i < n; i++) {
			if (s[i] == 'B')Blue.push_back(a[i]);
			else Red.push_back(a[i]);
		}
		sort(Blue.begin(), Blue.end());
		sort(Red.begin(), Red.end());
		int start = 1;
		for (auto kk : Blue) {
			if (kk >= start)start++;
			else break;
		}
		for (auto kk : Red) {
			if (kk > start)break;
			start++;
		}
		if (start == n + 1) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
}

E. Robot on the Board 1

Problem - E - Codeforces

Problem - E - Codeforces

 

문제

n X m 그리드가 주어질 때, LDUR 명령어를 수행하는 로봇이 있다. 로봇은 명령어를 수행하다가 n X m 그리드를 벗어나면 작동이 중지하는데, 명령어가 주어지고 최대로 명령어를 수행할 수 있는 시작 위치를 출력하는 문제

 

풀이

 

위아래로 최소,최대 범위를 지정하고 이 범위가 n을 넘거나, 양옆으로 최소,최대 범위를 지정하고 이 범위가 m을 넘으면 break 하고 가능한 범위 (직전 범위)를 이용해 시작 위치를 출력한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		cin >> s;
		int nown=0,nowm=0;
		int maxlr = 0, minlr = 0, maxdu = 0, mindu = 0;
		int lastMaxlr = 0, lastMinlr = 0, lastMindu = 0, lastMaxdu = 0;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == 'U') {
				nown++;
				maxdu = max(maxdu, nown);
			}
			else if (s[i] == 'D') {
				nown--;
				mindu = min(mindu, nown);
			}
			else if (s[i] == 'R') {
				nowm++;
				maxlr = max(maxlr, nowm);
			}
			else if(s[i]=='L'){
				nowm--;
				minlr = min(minlr, nowm);
			}
			int difn = maxdu - mindu, difm = maxlr - minlr;
			if (difn >= n || difm >= m) {
				break;
			}
			lastMaxlr = maxlr; lastMinlr = minlr;
			lastMaxdu = maxdu; lastMindu = mindu;
		}
		cout << 1 + lastMaxdu << ' ' << m - lastMaxlr << '\n';
	}
}

 

 

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

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