작년에 비해 예선 난이도가 쉬워졌다.
1. 친구들
\(N\)명의 사람들이 서 있다.
\(i\)번 사람은 자연수 \(D_i\)를 각각 가지고 있는데, \(i\)번 사람과 \(i+D_i\)번 사람이 서로 친구 관계임을 나타낸다.
(\(i_D+i > N\)일 경우는 무시한다)
A, B가 친구 관계이고 B, C가 친구 관계라면, A, C도 친구 관계이다.
친구 관계의 극대 그룹은 해당 그룹 내의 모든 사람들이 친구 관계이면서, 이 조건을 유지하는 가장 큰 그룹을 말한다.
극대 그룹의 개수를 알아내야 한다.
모든 친구 관계를 그래프의 간선이나 Union-Find등으로 합쳐서, 컴포넌트의 개수를 세면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
vector <int> graph[100001];
int cache[100001];
void DFS(int v)
{
cache[v] = 1;
int res = 1;
for (int nv : graph[v])
{
if (cache[nv]) continue;
DFS(nv);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
for (int tc = 1; tc <= t; tc++)
{
cin >> n;
for (int i = 0; i < n; i++) graph[i].clear();
for (int i = 0; i < n; i++) cache[i] = 0;
for (int i = 0; i < n; i++)
{
int a; cin >> a;
if (i + a >= n) continue;
graph[i].push_back(i + a);
graph[i + a].push_back(i);
}
int ans = 0;
for (int i = 0; i < n; i++)
{
if (cache[i]) continue;
DFS(i);
ans++;
}
cout << "Case #" << tc << endl;
cout << ans << endl;
}
}
|
cs |
2. 이진수
\(n\)비트로 구성된 이진수 \(A\)와, 자연수 \(t\)가 주어진다.
이를 이용해 새로운 \(n\)비트 이진수 \(B\)를 다음과 같은 규칙으로 만든다.
1. 만약 \(i>t\)이고, \(a_{i-t} = 1\)이면 \(b_i = 1\)이다.
2. 그렇지 않고 \(i \le n-t\)이고, \(a_{i+t} = 1\)이면 \(b_i = 1\)이다.
3. 그렇지 않으면 \(b_i = 0\)이다.
\(B\)와 \(t\)가 주어졌을 때, \(A\)를 복원해야 한다.
가능한 \(A\)가 여러가지라면, 그 중 가장 사전순으로 앞서는 것을 출력한다.
만약 \(B_i\)가 0이면, \(A_{i-t}\)와 \(A_{i+t}\)는 모두 0이어야 한다.
또, \(B_i\)에 영향을 주는 \(A\)의 비트가 1개뿐이고, 이를 \(A_j\)라고 하면, \(B_i = A_j\)여야 한다.
이런식으로 강제되는 비트들을 정하고 나서, 남은 비트들을 앞에서부터 차례로 채워주자.
사전순으로 가장 앞서는 것을 구해야 하므로 가능하면 0을 넣어주고, 0을 넣었을 때 \(A\)로 \(B\)를 만드는 것이 불가능할 경우에만 1을 넣어주면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, t;
string s;
int ans[50001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++)
{
cin >> n >> t;
cin >> s;
for (int i = 0; i < n; i++) ans[i] = -1;
for (int i = t; i < t + t && i < n; i++) ans[i] = s[i - t] - '0';
for (int i = n - 1 - t; i > n - 1 - t - t && i >= 0; i--) ans[i] = s[i + t] - '0';
for (int i = 0; i < n; i++)
{
if (s[i] == '0')
{
if (0 <= i - t) ans[i - t] = 0;
if (i + t < n) ans[i + t] = 0;
}
}
for (int i = 0; i < n; i++)
{
if (ans[i] != -1) continue;
if (0 <= i - t)
{
if (s[i - t] == '0')
{
ans[i] = 0;
continue;
}
if (0 > i - t - t || ans[i - t - t] == 0)
{
ans[i] = 1;
continue;
}
}
if (i + t < n)
{
if (s[i + t] == '0')
{
ans[i] = 0;
continue;
}
if (i + t + t >= n || ans[i + t + t] == 0)
{
ans[i] = 1;
continue;
}
}
ans[i] = 0;
}
cout << "Case #" << tc << endl;
for (int i = 0; i < n; i++) cout << ans[i];
cout << endl;
}
}
|
cs |
3. No Cycle
정점이 \(N\)개인 그래프가 있다. 이 그래프의 간선의 일부분은 방향성이 있고, 일부분은 없다.
전체 그래프에 사이클이 없도록, 방향성이 정해지지 않은 간선의 방향을 정해 출력하면 된다.
가능한 경우가 여러가지라면, 사전순으로 가장 앞서는 답을 출력한다.
방향성이 정해지지 않은 간선 \((u, v)\)가 있다고 하자.
만약 \(v\)에서 방향성이 있는 간선만 사용하여 \(u\)로 가는 경로가 존재한다면, 무조건 \((v, u)\)를 추가해야 한다.
그렇지 않으면 \((u, v)\)를 추가하면 된다.
시간복잡도는 \(O((N+M)\cdot K)\)이다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, m, k;
vector <int> graph[501];
vector <int> ans;
int cache[501];
bool find_x(int v, int x)
{
cache[v] = 1;
if (v == x) return true;
for (int nv : graph[v])
{
if (cache[nv]) continue;
if (find_x(nv, x)) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++)
{
ans.clear();
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
graph[i].clear();
}
for (int i = 0; i < m; i++)
{
int u, v; cin >> u >> v;
graph[u].push_back(v);
}
for (int i = 0; i < k; i++)
{
int u, v; cin >> u >> v;
memset(cache, 0, sizeof cache);
if (find_x(v, u))
{
ans.push_back(1);
graph[v].push_back(u);
continue;
}
ans.push_back(0);
graph[u].push_back(v);
}
cout << "Case #" << tc << endl;
for (int x : ans) cout << x;
cout << endl;
}
}
|
cs |
4. 예약 시스템
\(2 \times m\) 크기의 방이 있다. 이 방에 예약자 그룹들을 배정해 주려고 한다.
한 예약자 그룹은 5명 이상의 예약자로 구성되어 있고, 예약자들은 각각 한 방을 배정 받는다. 총 예약자 수는 \(2m\)이다.
같은 그룹의 예약자들은 서로 인접해 있어야 한다.
각 예약자 \(i\)는 스트레스 지수 \(w_i\)를 가진다.
만약 서로 다른 그룹의 예약자 둘 \(a, b\)가 인접해 있다면, \(w_a + w_b\)의 스트레스를 받게 된다.
예약자들을 적절히 배정했을 때, 스트레스의 총 합의 최소값을 구해야 한다.
스트레스의 합이 최소가 되려면, 서로 다른 예약 그룹끼리 인접하는 경우가 최소가 되어야 한다.
부분 문제를 차례로 풀어 나가 보자.
1. 모든 그룹의 예약자의 수가 짝수
모든 그룹이 다음과 같이 뭉쳐 있는 상태가 최적이다.
다른 그룹 또는 벽과 인접하는 사람이 그룹당 4명이므로, 그룹 당 가장 작은 스트레스값을 가지는 4명의 사람을 뽑아 가장자리에 배정시켜 주면 된다.
가장자리에 배정된 사람들 중 4명은 벽과 인접하게 되므로 스트레스를 받지 않게 된다. 가장자리에 있는 사람들 중 스트레스값이 가장 큰 4명을 벽 옆에 위치시켜주면 된다.
단, 한 그룹에서는 최대 2명만이 벽과 인접할 수 있음에 주의하면 된다.
2. 모든 그룹의 예약자의 수가 홀수
위의 그림과 같이 뭉쳐있는 상태가 최적이다.
다른 그룹 또는 벽과 인접하는 사람수가 역시 그룹당 4명인데, 그 중 1명은 다른 그룹과 인접하는 경우가 2가지이다.
가장 작은 스트레스값을 가지는 1명을 이 곳에 배치해 주면 된다.
그 외는 짝수일 때와 같다.
3. 제한 없음
위의 풀이와 거의 같은데, 1가지 귀찮은 예외가 생긴다.
예약자의 수가 홀수인 그룹이 없거나 4개 이상일 때는 문제가 없는데, 2개일 때는 다음과 같은 경우가 답일 때도 존재한다.
이를 잘 처리해주면 된다.
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, m;
vector <ll> s[20001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++)
{
cin >> n >> m;
int odd_cnt = 0;
for (int i = 0; i < n; i++)
{
s[i].clear();
int l; cin >> l;
for (int j = 0; j < l; j++)
{
ll w; cin >> w;
s[i].push_back(w);
}
sort(s[i].begin(), s[i].end());
if (l % 2 == 1) odd_cnt++;
}
ll ans = 0;
if (odd_cnt == 2)
{
ll res1 = 0, res2 = 0, res3 = 0;
// 두 끝이 모두 홀수, 한쪽만 홀수, 전부 짝수
vector <ll> odd_tmp;
vector <pll> even_tmp;
for (int i = 0; i < n; i++)
{
if (s[i].size() % 2 == 1)
{
res1 += s[i][0] * 2 + s[i][1];
res2 += s[i][0] * 2 + s[i][1];
res3 += s[i][0] * 2 + s[i][1];
odd_tmp.push_back(s[i][2] + s[i][3]);
res3 += s[i][2] + s[i][3];
}
else
{
res1 += s[i][0] * 2 + s[i][1] * 2
+ s[i][2] + s[i][3];
even_tmp.push_back({ s[i][0] + s[i][1], i });
even_tmp.push_back({ s[i][2] + s[i][3], i });
}
}
if (even_tmp.size() == 0)
{
ans = res1;
}
else
{
sort(odd_tmp.begin(), odd_tmp.end());
sort(even_tmp.begin(), even_tmp.end());
res2 += odd_tmp[0];
for (int i = 0; i < even_tmp.size() - 1; i++)
res2 += even_tmp[i].first;
if (even_tmp.size() == 2)
{
ans = min(res1, res2);
}
else
{
int sz = even_tmp.size();
if (even_tmp[sz - 1].second == even_tmp[sz - 2].second)
swap(even_tmp[sz - 3], even_tmp[sz - 2]);
for (int i = 0; i < even_tmp.size() - 2; i++)
res3 += even_tmp[i].first;
ans = min(res1, min(res2, res3));
}
}
}
else
{
vector <pll> tmp;
for (int i = 0; i < n; i++)
{
if (s[i].size() % 2 == 1)
{
ans += s[i][0] * 2 + s[i][1];
tmp.push_back({ s[i][2] + s[i][3], i });
}
else
{
tmp.push_back({ s[i][0] + s[i][1], i });
tmp.push_back({ s[i][2] + s[i][3], i });
}
}
sort(tmp.begin(), tmp.end());
int sz = tmp.size();
if (tmp[sz - 1].second == tmp[sz - 2].second)
{
swap(tmp[sz - 3], tmp[sz - 2]);
}
for (int i = 0; i < sz - 2; i++) ans += tmp[i].first;
}
cout << "Case #" << tc << endl;
cout << ans << endl;
}
}
|
cs |
5. 차이
\(N\)개의 변수가 있다.
이 변수들에 \(K\)개의 쿼리를 처리하려고 한다.
1. 두 변수의 차이가 얼마인지 알려준다.
2. 두 변수의 차이를 출력한다.
2번 쿼리에서 지금까지의 정보에 따라 다음과 같이 두 변수의 차이를 출력하면 된다.
1. 두 변수의 차이가 유일하게 정해질 때 : 그 값을 출력한다.
2. 두 변수의 차이를 알 수 없을 떄 : "NC"를 출력한다.
3. 두 변수의 차이가 하나로 정해질 수 없을 떄 : "CF"를 출력한다.
1번 쿼리로 인해 차이가 정해진 변수들을 Union-Find로 관리해주면 된다.
이 문제와 메우 비슷하다.
https://www.acmicpc.net/problem/3830
3830번: 교수님은 기다리지 않는다
교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000,
www.acmicpc.net
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, k;
int par[100001];
bool isCF[100001];
ll dist[100001];
int getPar(int a)
{
if (par[a] == a) return a;
int op = par[a];
int np = getPar(par[a]);
dist[a] += dist[op];
par[a] = np;
return np;
}
void merge(int a, int b, ll d)
{
int pa = getPar(a);
int pb = getPar(b);
if (pa == pb)
{
if (dist[b] - dist[a] != d)
{
isCF[pa] = true;
}
return;
}
par[pb] = pa;
dist[pb] = d + dist[a] - dist[b];
if (isCF[pa] || isCF[pb])
{
isCF[pa] = true;
isCF[pb] = true;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++)
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
par[i] = i;
isCF[i] = false;
dist[i] = 0;
}
cout << "Case #" << tc << "\n";
while (k--)
{
int o; cin >> o;
if (o == 1)
{
ll i, j, d; cin >> i >> j >> d;
merge(i, j, d);
}
else
{
int a, b; cin >> a >> b;
int pa = getPar(a);
int pb = getPar(b);
if (pa != pb)
{
cout << "NC" << "\n";
continue;
}
if (isCF[pa])
{
cout << "CF" << "\n";
continue;
}
cout << dist[b] - dist[a] << "\n";
}
}
}
}
|
cs |
'문제 풀이 > 그외' 카테고리의 다른 글
| Code Jam - Qualification Round 2021 (1) | 2021.03.28 |
|---|---|
| Round A 2021 - Kick Start 2021 (0) | 2021.03.21 |
| Google Kick Start - Round F 2020 (0) | 2020.09.27 |
| Google Kick Start - Round E 2020 (2) | 2020.08.23 |
| SCPC 2020 Round 1 (2) | 2020.08.22 |
