길이 \(n\)의 배열 \(a\)가 주어진다.
배열의 \([l, r]\) 구간을 선택, 원하는만큼 cyclically rotate하는 연산을 한 번 수행하여 얻을 수 있는 \(a_n - a_1\)의 최댓값을 구하는 문제이다.
다음과 같이 경우를 나눌 수 있다.
1) \(a_1, a_n\) 미포함: \(ans = a_n - a_1\)
2) \(a_1\)만 미포함: \(ans = max(a_2, a_3, ..., a_n) - a_1\)
3) \(a_n\)만 미포함: \(ans = a_n - min(a_1, a_2, ..., a_{n-1})\)
4) \(a_1, a_n\)을 모두 포함: \(ans = max_{1 \le i \le n}(a_{i-1} - a_i)\) (단, \(a_0 = a_n\))
|
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
32
33
34
|
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[0] = a[n];
int ans = a[n] - a[1];
for (int i = 2; i <= n; i++) {
ans = max(ans, a[i] - a[1]);
}
for (int i = 1; i <= n-1; i++) {
ans = max(ans, a[n] - a[i]);
}
for (int i = 1; i <= n; i++) {
ans = max(ans, a[i-1] - a[i]);
}
cout << ans << '\n';
}
return 0;
}
|
cs |
B. Mainak and Interesting Sequence
\(a\)와 \(p\)는 길이가 \(n\)인 배열이다.
배열 \(p\)의 원소 \(p_i\)의 값은 다음과 같이 정의된다.
\(p_i = \text{the bitwise XOR of all elements in}\) \(a\) \(\text{which are strictly less than } a_i\)
배열 \(p\)의 모든 원소가 0일 때 배열 \(a\)를 interesting하다고 한다.
\(a_1 + a_2 + ... + a_n = m\)을 만족하는 interesting한 배열 \(a\)를 찾는 문제이다. 단, \(a_i \gt 0\)이다.
배열 \(a\)에서 가장 작은 원소를 \(x\), 그 다음 작은 원소를 \(y\), 그 다음 작은 원소를 \(z\), ...라고 하자.
\(x\)는 배열 \(a\) 안에 반드시 짝수개 존재해야 한다.
만약 홀수개 존재한다면 \(y\) 입장에서 봤을 때 \(p\)의 원소가 0이 아니게 된다.
\(y\)도 반드시 짝수개 존재해야 한다.
\(x\)를 모두 XOR한 값이 0이므로 \(y\)가 홀수개 존재하면 \(z\) 입장에서 \(p\)의 원소가 0이 아니게 된다.
같은 이유로 \(z\), ...도 각각 짝수개 존재해야 한다.
단, 가장 큰 원소는 홀짝 개수 제한이 없다.
다음과 같이 경우를 나눌 수 있다.
1) \(n \gt m\): NO
2) \(n\)이 홀수: 1, 1, ..., 1, 1, \(m - n + 1\)
3) \(n\)이 짝수:
3-1) \(m\)이 짝수: 1, 1, ..., 1, \(\frac{m - n + 2}{2}\), \(\frac{m - n + 2}{2}\)
3-2) \(m\)이 홀수: NO
3-2 증명
\(n\)이 짝수, \(m\)이 홀수이면서 조건을 만족하는 배열 \(a\)가 존재한다고 가정하자.
\(m\)이 홀수이므로, 배열 \(a\)에는 어떤 홀수 \(x\)가 홀수개 존재해야 한다.
그런데 \(n\)이 짝수이므로 배열 \(a\)에 어떤 수 \(y\)가 홀수개 존재한다. (\(y \ne x\))
(위에서 증명한 정리에 의해) 이러한 배열은 존재할 수 없으므로 가정에 모순된다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n > m) {
cout << "No\n";
}
else {
if (n % 2) {
cout << "Yes\n";
for (int i = 0; i < n-1; i++) {
cout << 1 << ' ';
}
cout << m - n + 1 << '\n';
}
else {
if (m % 2) {
cout << "No\n";
}
else {
cout << "Yes\n";
for (int i = 0; i < n-2; i++) {
cout << 1 << ' ';
}
cout << (m - n + 2) / 2 << ' ';
cout << (m - n + 2) / 2 << '\n';
}
}
}
}
return 0;
}
|
cs |
C. Jatayu's Balanced Bracket Sequence
길이가 \(2n\)인 balanced bracket sequence \(s\)가 주어진다.
\(1 \le i \lt j \le 2n\)인 모든 \(i, j\)에 대해, \(s[i...j]\)가 balanced bracket sequence이면 \(i\)와 \(j\)를 잇는 간선을 그래프에 추가한다.
간선은 양방향이며 가중치가 붙지 않는다.
위 과정을 거쳐 만들어진 그래프의 component 개수를 구하는 문제이다.
\(i, j\)가 같은 component에 속하려면 다음 두 가지 조건을 만족해야 한다.
1) \(s[i], s[j]\)의 괄호 깊이가 같다.
2) \(i\)와 \(j\) 사이에 깊이가 더 낮은 괄호가 존재하지 않는다.
|
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
32
33
34
|
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
stack<int> st;
vector<int> a;
for (char ch: s) {
if (ch == '(') {
st.push(1);
a.push_back(st.size());
}
else {
st.pop();
}
}
int ans = 1;
for (int i = 1; i < (int)a.size(); i++) {
if (a[i] > a[i-1]) ans++;
}
cout << ans << '\n';
}
return 0;
}
|
cs |
\(n\)개의 정점과 \(m\)개의 간선으로 구성된 무방향, 가중치 없는 연결 그래프가 주어진다.
각 간선을 빨간색 또는 파란색 중 하나로 칠한다.
빨간 간선만 고려했을 때 component의 개수를 \(c_1\), 파란 간선만 고려했을 때 component의 개수를 \(c_2\)라고 하자.
\(c_1 + c_2\)의 최솟값을 구하는 문제이다.
\(m \le n + 2\) 조건이 눈에 띈다. 스패닝 트리 느낌이 난다.
빨간 간선으로만 이뤄진 그래프를 \(R\), 파란 간선으로만 이뤄진 그래프를 \(B\)라고 하자.
WLOG, \(R\)이 스패닝 트리일 때 정답이 되지 않을까? 정말 그런지 증명해보자.
증명
1. \(R\)에 cycle이 존재하는 경우
cycle에 포함된 어떤 간선 \(e\)를 \(R\)에서 \(B\)로 옮긴다.
이때 \(c_1\)은 변하지 않고 \(c_2\)는 최대 1만큼 감소한다.
2. \(R\)이 두 개 이상의 component로 구성된 경우
\(R\)의 서로 다른 component에 속해 있는 두 정점 \(u, v\)를 잇는 간선을 \(B\)에서 \(R\)로 옮긴다.
이때 \(c_1\)은 1만큼 감소하고 \(c_2\)는 최대 1만큼 증가한다.
\(\therefore\) 두 행동 모두 최적해를 악화시키지 않는다는 것을 알 수 있다.
\(R\)을 스패닝 트리로 만들었으므로 \(c_1 = 1\)이다.
이제 \(c_2\)를 최소화해야 하는데, 남은 간선의 개수는 최소 0개에서 최대 3개이다.
\(B\)에 cycle이 생기는 경우만 조심하면 된다.
\(B\)에 포함된 간선이 \(u-v, v-w, w-u\)라고 하자.
DFS spanning tree에 포함된 간선은 tree edge와 back edge로 나뉜다.
따라서, WLOG, \(u, v\)가 \(w\)의 조상이다.
\(w\)의 부모를 \(p\)라고 하자.
\(B\)의 \(v-w\)와 \(R\)의 \(w-p\)를 교환함으로써 문제를 해결할 수 있다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
int n, m;
vector<int> par;
vector<int> depth;
vector<vector<pii> > adj;
vector<int> ans;
void dfs(int u, int p, int d) {
par[u] = p;
depth[u] = d;
for (auto [v, idx]: adj[u]) {
if (v != p && depth[v] == -1) {
dfs(v, u, d+1);
ans[idx] = 1;
}
}
}
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) {
cin >> n >> m;
par.clear(); par.resize(n+1);
depth.clear(); depth.resize(n+1, -1);
adj.clear(); adj.resize(n+1);
ans.clear(); ans.resize(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
dfs(1, 0, 0);
if (m == n + 2) {
vector<int> vertex;
for (int i = 1; i <= n; i++) {
for (auto [j, idx]: adj[i]) {
if (ans[idx] == 0) {
vertex.push_back(i);
vertex.push_back(j);
}
}
}
sort(all(vertex));
vertex.erase(unique(all(vertex)), vertex.end());
if (vertex.size() == 3) {
int w = vertex[0];
int v = vertex[1];
if (depth[w] < depth[v]) swap(w, v);
int idx1, idx2;
for (auto [i, idx]: adj[w]) {
if (i == v) idx1 = idx;
if (i == par[w]) idx2 = idx;
}
swap(ans[idx1], ans[idx2]);
}
}
for (int i: ans) {
cout << i;
}
cout << '\n';
}
return 0;
}
|
cs |
'Codeforces' 카테고리의 다른 글
| Codeforces #763 (0) | 2022.01.02 |
|---|---|
| Codeforces Educational #120 (0) | 2022.01.02 |
| Codeforces Global #18 (0) | 2021.12.26 |
| Codeforces Educational #82 (0) | 2021.12.26 |
| Codeforces #619 (0) | 2021.12.23 |