티스토리 뷰

ps

codeforces round 813 (div.2)

logwns 2022. 8. 20. 23:24

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$보다 큰 값의 개수가 답이 된다.

 

 

코드 :

<hide/>
#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$형태가 최대가 된다.

 

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

 

 

코드 :

<hide/>
#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$부터 그 위치까지 검사하면 된다. 만약 없다면 수열이 단조 증가한다는 뜻이므로 끝내면 된다.

 

 

코드 :

<hide/>
#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

 

'ps' 카테고리의 다른 글

codeforces round 815 (div.2)  (0) 2022.08.30
codeforces round 814 (div.2)  (0) 2022.08.25
codeforces round 812 (div.2)  (0) 2022.08.17
educational codeforces round 133  (0) 2022.08.11
codeforces round 811 (div.3)  (0) 2022.08.06
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함