Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) 1495 -> 1508

Dashboard - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

Dashboard - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

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

 

 

A. Divide and Multiply

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

길이가 n인 정수 배열이 주어진다 각 2의 배수인 a[i]와 i != j인 아무 j를 골라 a[i]/=2 , a[j]*2를 할 수 있다. 원하는 만큼 여러번 할 수 있을 때 전체 원소의 최대 합을 구하는 문제

 

풀이

 

2로 나눌 수 있는 원소들은 미리 나누고, 정렬 후 가장 큰 값에 곱한다

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[16];
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  start = 1;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			while (a[i] % 2 == 0) {
				a[i] /= 2;
				start *= 2LL;
			}
		}
		sort(a, a + n);
		long long sum = 0;
		for (int i = 0; i < n - 1; i++)sum += a[i];
		sum += (a[n - 1] * start);
		cout << sum << '\n';
	}
}

 

 

B. William the Vigilant

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

a,b,c 로 이루어진 string s와 q가 주어진다. q번 만큼 지정한 인덱스 위치에 문자를 바꾸는 연산을 할 때, 각 연산마다 연속된 substring중에 abc가 없도록 바꿔야하는 최소 인덱스의 개수를 출력하는 문제

 

풀이

우선 원래 배열에서 연속된 abc의 개수를 센다. 이후 지정한 인덱스 -2~0 까지 시작위치로 잡아서 바꾸기 전에 abc가 있다면 개수를 빼주고 , 바꾼후에 abc가 있다면 더해줘서 이 개수 값을 출력한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, q;
	cin >> n >> q;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i + 2 >= n)break;
		if (s[i] < s[i + 1] && s[i + 1] < s[i + 2]) {
			cnt++;
			i = i + 2;
		}
	}
	while (q--) {
		int pos; char c;
		cin >> pos >> c;
		pos--;
		if (s[pos] == c) {
			cout << cnt << '\n';
			continue;
		}
		for (int i = max(0, pos - 2); i <= pos; i++) {
			if (i + 2 >= n)break;
			if (s[i] < s[i + 1] && s[i + 1] < s[i + 2])cnt--;
		}
		s[pos] = c;
		for (int i = max(0, pos - 2); i <= pos; i++) {
			if (i + 2 >= n)break;
			if (s[i] < s[i + 1] && s[i + 1] < s[i + 2])cnt++;
		}
		cout << cnt << '\n';
	}
 
}

 

C. Complex Market Analysis

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

n길이의 배열과 e가 주어진다. 여기서 아래를 만족하는 (i,k)쌍의 갯수를 구하는 문제

1 <= i,k

i+e*k <=n

a[i]*a[i+e]*a[i+2*e]*...a[i+k*e] 가 소수

 

 

 

풀이

 

각 e 간격마다 새로운 벡터에 수를 담고, 벡터 기준으로 v[i]가 소수라면 양옆에 1의 개수를 세서 더해준다.

왼쪽에나 오른쪽에만 1이 있을때는 각 갯수를 더해주면되고 , 양쪽에 1이 있다면 왼쪽 1의 갯수 * 오른쪽 1의 갯수를 한번 더 더해준다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[200001];
vector<int> v[200001];
bool check[200001];
bool c[1000001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	c[1] = true;
	for (long long i = 2; i < 1000001; i++) {
		if (c[i] == false) {
			for (long long j = i * i; j < 1000001; j += i) {
				c[j] = true;
			}
		}
	}
	int T;
	cin >> T;
	while (T--) {
		int n,e;
		cin >> n>>e;
		for (int i = 1; i <= n; i++) {
			v[i].clear();
			check[i] = false;
		}
		for (int i = 1; i <= n; i++)cin >> a[i];
		for (int i = 1; i <= n; i++) {
			if (check[i])continue;
			for (int j = 0; j <= n; j++) {
				int end = i + e * j;
				if (end> n)break;
				check[end] = true;
				v[i].push_back(a[end]);
			}
		}
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			if (v[i].size() == 0)break;
			vector<pair<int, long long>> temp;
			for (int j = 0; j < v[i].size(); j++) {
				if (v[i][j] == 1) {
					long long cnt = 0;
					int l = j, r = j;
					for (int k = j; k < v[i].size(); k++) {
						if (v[i][k] == 1) {
							cnt++;
							r++;
						}
						else break;
					}
					r--;
					j = r;
					temp.push_back({ 1,cnt });
				}
				else temp.push_back({ v[i][j],1 });
			}
			for (int j = 0; j < temp.size(); j++) {
				if (c[temp[j].first] == false) {
					int tcnt = 0;
					if (j - 1 >= 0) {
						if (temp[j - 1].first == 1) {
							ans += temp[j - 1].second;
							tcnt++;
						}
					}
					if (j + 1 < temp.size()) {
						if (temp[j + 1].first == 1) {
							ans += temp[j + 1].second;
							tcnt++;
						}
					}
					if (tcnt == 2) {
						ans += temp[j - 1].second * temp[j + 1].second;
					}
				}
			}
		}
		cout << ans << '\n';
	}
 
 
}

 

 

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

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