Codeforces Round #837 (Div 2.)

https://codeforces.com/contest/1771

 

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

 

 

A. Hossam and Combinatorics

 

 

요약

 

 

n개의 정수로 이루어진 수열이 주어진다. $\left| a_{i} - a_{j}\right|$이 수열에서 최대인 쌍 (i, j)의 갯수를 구한다.

---

1. $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, 0이 아닌 경우로 나누어 풀 수 있다. 만약 $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, n개의 정수가 모두 같은 수일 때이므로 답은 $n *(n-1)$이 된다.

 

2. $\left| a_{i} - a_{j}\right|$의 최댓값이 0이 아닌 경우는 두 경우 중 한 가지이다.
첫 째, $a_i$가 최솟값이고, $a_j$가 최댓값인 경우

둘 째, $a_i$가 최댓값이고, $a_j$가 최솟값인 경우

 

2. 이때는, 최솟값의 개수 * 최댓값의 개수 * 2가 정답이 된다.

#include <bits/stdc++.h>
using namespace std;

long long t, n;
long long arr[100000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		long long m = 0x3f3f3f3f, M = 0, max_diff, m_cnt = 0, M_cnt = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			m = min(m, arr[i]);
			M = max(M, arr[i]);
		}
		max_diff = M - m;
		if (max_diff == 0) cout << n * (n - 1) << '\n';
		else {
			for (int i = 0; i < n; i++) {
				if (arr[i] == M) M_cnt++;
				if (arr[i] == m) m_cnt++;
			}
			cout << M_cnt * m_cnt * 2 << '\n';
		}
	}
	return 0;
}

 

 

 

B. Hossam and Friends

 

 

요약

 

n명의 친구들 중 서로 친하지 않은 m개의 쌍이 주어진다. 모두 친한 사람들로 이루어진 연속된 부분수열의 개수를 구한다.

---

1. 스위핑의 개념으로 i = 1부터 i = n까지 i에서 시작하는 연속 부분수열 중 최댓값을 구한다.  

 

2. i보다 큰 수 중 i와 친하지 않은 가장 가까운 친구를 table[i]에 저장한다. 

 

3. i = n 부터 시작하여 i = 1까지 반복문을 돌며 table[i] = min(table[i], table[i+1]) 연산을 수행한다.
만약 1 과 5가 서로 친하지 않고, 2 와 3이 서로 친하지 않는다면, (1, 2, 3, 4)와 같은 수열은 이루어질 수 없다. 2 와 3이 서로 친하지 않기 때문이다. 따라서 table[1]에는 3이 저장되어야 한다.

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long t, n, m, ans;
long long table[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		ans = 0;
		memset(table, INF, sizeof(table));
		for (int i = 0; i < m; i++) {
			long long a, b;
			cin >> a >> b;
			table[min(a, b)] = min(table[min(a, b)], max(a, b));
		}
		for (int i = n; i >= 1; i--) {
			if (i == n) ans += 1;
			else {
				table[i] = min(table[i], table[i + 1]);
				if (table[i] == INF) ans += (n - i + 1);
				else ans += (table[i] - i);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

 

 

 

C. Hossam and Trainees

 

 

요약

 

n개의 정수가 주어졌을 때, n개 중 2개의 정수를 고른 쌍 중 서로소가 아닌 것이 있는지를 판별한다.

---

1. n개의 정수를 받으며 모든 소인수를 set에 넣어준다.

 

2. 만약 이미 들어있는 소인수가 존재한다면, 서로소가 아닌 쌍이 존재하는 것이다.

 

3. 소인수분해 과정은 다음 글을 참고한다.
https://int-p.tistory.com/21

정수의 소인수분해 알고리즘

#include <bits/stdc++.h>
using namespace std;

long long t, n;
vector <long long> primeNum;
int table[100001];
set <long long> s;

void pre();
bool check(long long k);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	pre();
	cin >> t;
	while (t--) {
		cin >> n;
		s.clear();
		int flag = 0;
		for (int i = 0; i < n; i++) {
			long long a;
			cin >> a;
			if (flag == 1) continue;
			if (check(a) == true) flag = 1;
		}
		if (flag == 1) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

void pre() {
	for (long long i = 2; i * i <= 1000000000; i++) {
		if (table[i] == 0) {
			primeNum.push_back(i);
			table[i] = 1;
			for (long long j = i * i; j * j <= 1000000000; j += i) table[j] = 1;
		}
	}
}

bool check(long long k) {
	for (int i = 0; i < primeNum.size(); i++) {
		long long now = primeNum[i];
		if (now > k) break;
		if (k % now == 0) {
			if (s.count(now)) return true;
			s.insert(now);
			while (1) {
				if (k % now == 0) k /= now;
				else break;
			}
		}
	}
	if (k != 1) {
		if (s.count(k)) return true;
		s.insert(k);
	}
	return false;
}

 

 

 

D. Hossam and (sub-)palindromic tree

 

 

요약

 

정점에 문자가 들어있는 가중치가 없는 트리가 주어진다. s(v, u)를 v에서 u로 가는 경로에 있는 문자를 모두 포함한 문자열이라고 할 때, s(v, u)의 sub-pallindrome의 최대 길이를 구한다.

---

1. DP로 풀이한다. table[i][j]를 i에서 j로 가는 경로에 있는 문자열 중 sub-pallindrome의 최대 길이라고 하자. i에서 j로 가는 유일한 경로에 속해있는 정점 중, 거리가 1 차이나는 정점을 vertex[i][j]라고 할 때, table[i][j]의 값은 다음 세 가지 중 한 경우이다.

첫 째, table[i][j] = table[i][vertex[j][i]]

둘 째, table[i][j] = table[vertex[i][j]][j]

셋 째, table[i][j] = table[vertex[i][j]][vertex[j][i]] + (i 정점의 문자 == j 정점의 문자) * 2

 

2. 선형 구조에서 sub-pallindrome의 최대 길이를 다음과 같이 구하는 것과 유사하다.

table[i][j] = max({table[i+1][j], table[i][j-1], table[i+1][j-1] + (s[i] == s[j]) * 2})

 

3. DFS를 통해 vertex[i][j]를 먼저 채우고, i 정점과 j 정점의 거리가 짧은 순으로 table[i][j]를 채우면 정답을 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2001;

int t, N, ans;
char arr[MAX];
vector <int> graph[MAX];
int vertex[MAX][MAX], table[MAX][MAX];
vector<pair<int, int>> len[MAX];
string s;

void DFS(int start, int now, int val, int par, int l);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> N;
		cin >> s;
		ans = 0;
		for (int i = 1; i <= N; i++) {
			arr[i] = s[i - 1];
			graph[i].clear();
			len[i - 1].clear();
		}
		for (int i = 0; i < N - 1; i++) {
			int A, B;
			cin >> A >> B;
			graph[A].push_back(B);
			graph[B].push_back(A);
		}
		for (int i = 1; i <= N; i++) DFS(i, i, -1, -1, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < len[i].size(); j++) {
				int a = len[i][j].first;
				int b = len[i][j].second;
				if (i == 0) table[a][b] = 1;
				else if (i == 1) table[a][b] = 1 + (arr[a] == arr[b]);
				else {
					int x = table[a][vertex[b][a]];
					int y = table[vertex[a][b]][b];
					int z = table[vertex[a][b]][vertex[b][a]] + (arr[a] == arr[b]) * 2;
					table[a][b] = max({ x,y,z });
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) ans = max(ans, table[i][j]);
		}
		cout << ans << '\n';
	}
	return 0;
}

void DFS(int start, int now, int val, int par, int l) {
	if (l == 1) val = now;
	if (l > 1) vertex[start][now] = val;
	len[l].push_back({ start, now });
	for (int i = 0; i < graph[now].size(); i++) {
		if (graph[now][i] == par) continue;
		DFS(start, graph[now][i], val, now, l + 1);
	}
}