티스토리 뷰
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 |