codeforces round 813 (div.2)

A. Wonderful Permutation

 

문제 :

$1$부터 $n$까지 각 값이 한번씩 등장하는 길이가 $n$인 수열 $p_1, p_2, ..., p_n$과 자연수 $k(k\leq n)$이 있다. 이 중 임의의 $i, j (1\leq i < j \leq n)$에 대하여 $p_i$와 $p_j$를 교환할 수 있다. 이때 $p_1 + p_2 + ... + p_k$를 최소로 하려면 몇번의 연산을 해야되는지 구하면 된다.

 

 

풀이 :

$k$개의 값이 최소가 되려면 $1 + 2 + ... + k$일 때가 최소이므로 $p_1, p_2, ..., p_k$ 중 $k$보다 큰 값의 개수가 답이 된다.

 

 

코드 :

cpp

열기 줄바꿈

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, k;
	cin >> n >> k;
	int x, cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (i<k && x>k) cnt++;
	}
	cout << cnt << '\n';
	return;
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

B. Woeful Permutation

 

 

문제 :

임의의 $n$에 대하여 $lcm(1,p_1) + lcm(2,p_2) + ... + lcm(n,p_n)$을 최대로 하는 수열 $p$를 찾으면 된다.

 

 

풀이 :

$n$이 홀수일 때 : $1\ 3\ 2\ 5\ 4\ ...\ n\ n-1$형태가 최대가 된다.

$n$이 짝수일 때 : $2\ 1\ 4\ 3\ ...\ n\ n-1$형태가 최대가 된다.

 

(+그냥 이렇게 하면 되겠지 하고 풀긴 했는데 왜 이렇게 해야 최대인지 알아봐야겠다ㅠ)

 

 

코드 :

cpp

열기 줄바꿈

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	if (n % 2) {
		cout << 1 << ' ';
		for (int i = 2; i <= n; i++) {
			if (i % 2 == 0) cout << i + 1 << ' ';
			else cout << i - 1 << ' ';
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (i % 2) cout << i + 1 << ' ';
			else cout << i - 1 << ' ';
		}
	}
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

C. Sort Zero

 

문제 :

길이가 $n$인 수열 $a_1, a_2, ..., a_n$이 있다.($1\leq a_i \leq n$) 임의의 $x$에 대하여 $a_i=x$인 $a_i$들을 $0$으로 만드는 연산이 있다. 이때 수열이 단조 증가하려면 최소 몇 번의 연산을 해야 하는지 구하면 된다.

 

 

풀이 :

수열이 단조 증가라면 가장 마지막 원소($a_n$)가 가장 큰 값이 되어야 한다. 뒤에서부터 앞으로 보면서 ($a_n \rightarrow a_1$) 현재의 원소보다 이전의 원소가 큰 부분이 있는지 검사한다. 만약 그 위치가 $i$라 하면 ($a_{i-1} > a_i$) $1$부터 $i-1$의 값들은 전부 $0$으로 한다. 여기서 $i$의 위치를 기억해두고 다시 $n$부터 이 위치까지 $a_{i-1} > a_i$인 부분이 있는지 검사한다.($0$으로 바꾸는 과정에서 $i+1 \sim n$의 위치에서 값이 $0$으로 바뀔 수도 있기 때문에) 만약 있다면 다시 그 위치 이전의 값들을 전부 $0$으로 바꿔주고 다시 $n$부터 그 위치까지 검사하면 된다. 만약 없다면 수열이 단조 증가한다는 뜻이므로 끝내면 된다.

 

 

코드 :

cpp

열기 줄바꿈

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> ar(n);
	vector<bool> stat(n + 1, false);
	for (int i = 0; i < n; i++) cin >> ar[i];
 
	int flag = 0, ans = 0;
	while (1) {
		bool chk = false;
		for (int i = n - 1; i > flag; i--) {
			if (stat[ar[i]] && !stat[ar[i - 1]] || !stat[ar[i - 1]] && ar[i - 1] > ar[i]) {
				flag = i - 1;
				chk = true;
				break;
			}
		}
		if (!chk) break;
		for (int i = flag; i >= 0; i--) {
			if (!stat[ar[i]]) stat[ar[i]] = true, ans++;
		}
	}
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	for (cin >> t; t--;) solve();
	return 0;
}

 

---

 

D. Empty Graph

 

문제 :

길이가 $n$인 수열이 있고 이 수열에서 임의의 $a_i$를 $x(1 \leq x \leq 10^9)$로 최대 $k$번 변경할 수 있다.

$n$개의 정점을 가진 무방향 완전 그래프가 있는데 임의의 $l,r (1\leq l < r \leq n)$에 대하여 정점$l$에서 정점$r$로 이동하는데 드는 비용은 $min(a_l, a_{l+1}, ..., a_r)$이다. $d(u,v)$를 $u$에서 $v$로 가는 최단경로라 할 때 $max\ d(u,v) (1\leq u < v \leq n)$을 구하면 된다.

 

 

풀이 :

 

---

 

E1. LCM Sum (easy version)

E2. LCM Sum (hard version)

 

---

F. Triameter