Codeforces-Round-624-Div3

A. Add Odd or Subtract Even

필요한 지식

1. 구현

접근

1. a<b 인 경우 a-b가 홀수인경우는 1을 출력하고 짝수인 경우는 2를 출력한다.
2. a>b 인경우 b-a가 홀수인경우 2를 짝수인경우 1을 출력한다.
3. a==b 인경우 0을 출력한다.

코드(C++)

#include <iostream>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		int a, b; cin >> a >> b;
		if (a < b) {
			if ((b - a) % 2 == 1) {
				cout << 1 << "\n";
			}
			else if ((b - a) % 2 == 0) {
				cout << 2 << "\n";
			}
		}
		else if (a > b) {
			if ((a - b) % 2 == 1) {
				cout << 2 << "\n";
			}
			else if ((a - b) % 2 == 0) {
				cout << 1 << "\n";
			}
		}
		else if (a == b) cout << 0 << "\n";
	}
	return 0;
}

B. WeirdSort

필요한 지식

1. 구현
2. 버블 소트

접근

• 버블 소트를 진행 하되, P배열에 있는 원소를 확인 후, 현재 자리를 swap할 수 있다면 swap하고 아니라면 "NO"를 출력하게 한다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int chk[101];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		memset(chk, 0, sizeof(chk));
		int n, m; cin >> n >> m;
		vector<int>v, a, p;
		for (int i = 0; i < n; i++) {
			int x; cin >> x;
			v.push_back(x);
			a.push_back(x);
		}
		sort(a.begin(), a.end());
		for (int i = 0; i < m; i++) {
			int x; cin >> x; chk[x - 1] = 1;
		}
		sort(p.begin(), p.end());
		bool flag = true;
		for (int i = 0; i < v.size(); i++) {
			if (!flag) break;
			for (int j = 0; j < v.size() - i - 1; j++) {
				if (!flag) break;
				if (v[j] > v[j + 1]) {
					if (chk[j] == 0) {
						flag = false;
						break;
					}
					int temp = v[j];
					v[j] = v[j + 1];
					v[j + 1] = temp;
				}
			}
		}
		for (int i = 0; i < v.size();i++) {
			if (v[i] != a[i]) {
				flag = false;
				break;
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

C. Perform the Combo

필요한 지식

1. 구간 합

접근

• sum[i][26] : i번째 문자까지 진행했을 때 눌린 알파벳의 개수 로 지정하고
• 0~입력받은 문자열의 길이만큼 구간합을 구한다.
• m개의 틀린위치를 저장한 벡터를 돌면서 구간합 연산으로 결과 배열에 계속 합해준다.
• 초기화를 sum배열 전체를 계속 해주게되면 시간초과가 발생한다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
int sum[200001][27],res[27];
int n, m;
void init() {
	for (int i = 0; i <= n; i++) memset(sum[i], 0, sizeof(sum[i]));
	memset(res, 0, sizeof(res));
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		vector<int>v;
		string s; cin >> s;
		for (int i = 0; i < m; i++) {
			int x; cin >> x; v.push_back(x);
		}
		//get sum array
		sum[1][s[0] - 97] = 1;
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < 26; j++) sum[i][j] += (sum[i-1][j]);
			sum[i][s[i-1] - 97] += 1;
		}
		int prev = 0;
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < 26; j++) {
				res[j] += (sum[v[i]][j]);
			}
			prev = v[i]-1;
		}
		for (int j = 0; j < 26; j++) {
			res[j] += sum[n][j];
		}
		for (int i = 0; i < 26; i++) {
			cout << res[i] << " ";
		}
		cout << "\n";
		init();
	}
	return 0;
}

결과