A - Subset Mex
Problem - A - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
이 배열의 모든 원소들을 2개의 배열 \(A, B\)로 나눴을 때, \(MEX(A) + MEX(B)\)의 최대값을 구해야 한다.
\(n\)에 등장하는 수들의 개수를 세고, 이를 \(cnt_i\)라고 하자.
\(MEX(A)\)는 \(cnt_i = 0\)인 가장 작은 \(i\),
\(MEX(B)\)는 \(cnt_i \le 1\)인 가장 작은 \(i\)이다.
|
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
|
#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;
int cnt[101];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
cin >> n;
for (int i = 0; i < n; i++)
{
int x; cin >> x;
cnt[x]++;
}
int x = 0;
int a = 0, b = 0;
while (cnt[x] >= 2)
{
x++;
a = x, b = x;
}
while (cnt[x] >= 1)
{
x++;
b = x;
}
cout << a + b << '\n';
}
}
|
B - Maximum Product
Problem - B - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
이 배열에서 서로 다른 인덱스의 원소 5개를 골라, 그 곱이 최대가 되도록 해야 한다.
\(n = 5\)라면, 답이 정해져 있다.
원소가 모두 음수라면, 가장 절대값이 작은 값 5개를 곱한 것이 답이다.
그렇지 않다면 곱을 0 이상으로 만들 수 있다.
수들을 0 이상의 수 \(A\)와 음수 \(B\)로 나눈 다음 절대값이 큰 순으로 정렬하자.
다음 중 하나가 답이다.
1. \(A\)에서 절대값이 큰 5개 선택
2. \(A\)에서 3개, \(B\)에서 2개 선택
3. \(A\)에서 1개, \(B\)에서 4개 선택
|
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
|
#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 <ll> v1, v2;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
v1.clear();
v2.clear();
int n; cin >> n;
for (int i = 0; i < n; i++)
{
ll a; cin >> a;
if (a >= 0) v1.push_back(a);
else v2.push_back(a);
}
if (n == 5)
{
ll ans = 1;
for (ll x : v1) ans *= x;
for (ll x : v2) ans *= x;
cout << ans << '\n';
continue;
}
sort(v1.rbegin(), v1.rend());
sort(v2.begin(), v2.end());
if (v1.empty())
{
ll ans = 1;
for (int i = 0; i < 5; i++)
ans *= v2[v2.size() - 1 - i];
cout << ans << '\n';
continue;
}
ll ans = numeric_limits<ll>::min();
if (v1.size() >= 1 && v2.size() >= 4)
{
ll res = v1[0] * v2[0] * v2[1] * v2[2] * v2[3];
ans = max(ans, res);
}
if (v1.size() >= 3 && v2.size() >= 2)
{
ll res = v1[0] * v1[1] * v1[2] * v2[0] * v2[1];
ans = max(ans, res);
}
if (v1.size() >= 5)
{
ll res = v1[0] * v1[1] * v1[2] * v1[3] * v1[4];
ans = max(ans, res);
}
cout << ans << '\n';
}
}
|
C - Link Cut Centroids
Problem - C - Codeforces
codeforces.com
트리가 주어진다.
이 트리에 있는 간선을 하나 제거한 다음, 임의의 간선을 하나 추가해야 한다.
결과 그래프는 트리여야 하고, 유일한 센트로이드를 가져야 한다.
트리에서 센트로이드는 최대 2개 있을 수 있다. 2개라면 이 두 센트로이드는 간선으로 연결되어 있다.
센트로이드가 2개이고 이를 각각 \(u, v\)라고 하자.
\(v\) 쪽에 있는 간선을 하나 제거한 다음 \(u\)에 붙이면 \(u\)가 유일한 센트로이드가 된다.
|
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
|
#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;
ll a[100001];
ll d[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
ll sum = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (i)
{
d[i] = a[i] - a[i - 1];
if (d[i] >= 0) sum += d[i];
}
}
ll res = a[0] + sum;
if (res >= 0) res = (res + 1) / 2;
else res = res / 2;
cout << res << '\n';
int q; cin >> q;
while (q--)
{
ll l, r, x; cin >> l >> r >> x;
l--, r--;
if (l == 0) a[0] += x;
else
{
if (d[l] >= 0) sum -= d[l];
d[l] += x;
if (d[l] >= 0) sum += d[l];
}
if (r + 1 < n)
{
if (d[r + 1] >= 0) sum -= d[r + 1];
d[r + 1] -= x;
if (d[r + 1] >= 0) sum += d[r + 1];
}
ll res = a[0] + sum;
if (res >= 0) res = (res + 1) / 2;
else res = res / 2;
cout << res << '\n';
}
}
|
D - Three Sequences
Problem - D - Codeforces
codeforces.com
\(n\)길이의 배열 \(a\)가 주어진다.
다음을 만족하는 배열 \(b, c\)를 만들자.
1. \(b_i + c_i = a_i\)
2. \(b\)는 비내림차순
3. \(c\)는 비오름차순
이 때, \(b, c\)의 모든 원소의 최대값을 최소화 하고, 그 값을 알아내야 한다.
\(q\)개의 쿼리가 주어진다.
각 쿼리마다 구간 \([l,r]\)에 \(x\)를 더한다음, 문제의 답을 출력해야 한다.
\(b_1\)을 0으로 고정해보자.
\(c_1 = a_1\)이고, 그 이후의 값들은 다음과 같이 정해진다.
1. \(a_{i+1} - a_i \ge 0\)
\(b_{i+1} = b_i+a_{i+1} - a_i\)
\(c_{i+1} = c_i\)
2. \(a_{i+1} - a_i \lt 0\)
\(b_{i+1} = b_i\)
\(c_{i+1} = c_i+a_{i+1} - a_i\)
그러면 문제의 답이 \(\lceil \frac {a_1+b_n}{2} \rceil \) 라는 사실을 알 수 있다.
이를 계산하기 위해서는 \(a_1\)와 \(b_n\)을 알아야 하는데, \(b_n\)은 \(a\)에서 인접한 원소의 차이가 양수인 값들만 더한 값이다.
따라서 \(a\)의 인접한 원소의 차이만 따로 저장하고, 이를 \(d\)라고 하자.
각 쿼리가 수행될 때마다 \(d_l\)과 \(d_{r+1}\) 두 값만이 변하게 되므로 쿼리마다 답을 \(O(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
|
#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;
ll a[100001];
ll d[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
ll sum = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (i)
{
d[i] = a[i] - a[i - 1];
if (d[i] >= 0) sum += d[i];
}
}
ll res = a[0] + sum;
if (res >= 0) res = (res + 1) / 2;
else res = res / 2;
cout << res << '\n';
int q; cin >> q;
while (q--)
{
ll l, r, x; cin >> l >> r >> x;
l--, r--;
if (l == 0) a[0] += x;
else
{
if (d[l] >= 0) sum -= d[l];
d[l] += x;
if (d[l] >= 0) sum += d[l];
}
if (r + 1 < n)
{
if (d[r + 1] >= 0) sum -= d[r + 1];
d[r + 1] -= x;
if (d[r + 1] >= 0) sum += d[r + 1];
}
ll res = a[0] + sum;
if (res >= 0) res = (res + 1) / 2;
else res = res / 2;
cout << res << '\n';
}
}
|
E - Deleting Numbers
Problem - E - Codeforces
codeforces.com
\(1\) 부터 \(n\)까지의 정수가 있는 집합이 있고, 이 중 \(x\)가 뭔지 알아내야 한다.
이를 위해 최대 10000번의 쿼리를 사용할 수 있다.
A \(a\) : 집합에 \(a\)의 배수의 개수를 리턴한다.
B \(a\) : 집합에 \(a\)의 배수의 개수를 리턴하고, \(x\)를 제외한 \(a\)의 배수를 모두 삭제한다.
C \(a\) : \(x = a\)임을 알아냈을 때 사용한다.
B 쿼리에서 \(a > 1\)이여야 한다.
먼저 \(\sqrt n\)이하의 모든 소수 \(p\)에 대해 B \(p\)를 실행하고, A \(1\)을 실행하면 삭제 된 수가 있는지 여부를 알 수 있다.
삭제된 수가 있다면, \(x\)는 \(\sqrt n\)이하의 소수 중 A \(p\)를 실행했을 때 0이 아닌 수들을 소인수로 가지고, 추가로 \(\sqrt n\)초과의 소수 중 최대 하나를 소인수로 가진다.
그렇지 않다면, \(x\)는 \(\sqrt n\)초과의 소수이거나 1이다.
이분탐색이나 sqrt Decomposition등을 이용해 알아낼 수 있다.
100000이하의 소수는 9592개이고, \(\sqrt {100000} < 317\)이므로 10000번 이내에 답을 알아낼 수 있음을 알 수 있다.
|
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
|
#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;
int ett[100001];
vector <int> p;
set <int> st;
int query(char c, int n)
{
cout << c << ' ' << n << endl;
int res; cin >> res;
return res;
}
int main()
{
cin >> n;
if (n == 1)
{
cout << "C 1" << endl;
return 0;
}
for (int i = 2; i <= n; i++)
{
if (ett[i]) continue;
p.push_back(i);
for (int j = i + i; j <= n; j += i)
ett[j] = 1;
}
int i = 0;
for (; p[i] * p[i] <= n; i++)
{
query('B', p[i]);
for (int j = p[i]; j <= n; j += p[i]) st.insert(j);
}
int cnt = n - st.size();
int res = query('A', 1);
if (res != cnt)
{
ll ans = 1;
vector <int> vec;
for (int i = 0; p[i] * p[i] <= n; i++)
{
int res = query('A', p[i]);
if (res) vec.push_back(p[i]), ans *= p[i];
}
for (int x : vec)
{
while (ans * x <= n)
{
int res = query('A', ans * x);
if (res == 0) break;
ans *= x;
}
}
for (; i < p.size(); i++)
{
if (ans * p[i] > n) break;
int res = query('A', ans * p[i]);
if (res) ans *= p[i];
}
cout << "C " << ans << endl;
return 0;
}
int mn = i;
for (; i < p.size(); i++)
{
query('B', p[i]);
cnt--;
if (i % 100 == 0 || i == p.size() - 1)
{
int res = query('A', 1);
if (res > cnt)
{
for (int j = max(mn, i - 99); j <= i; j++)
{
int res = query('A', p[j]);
if (res)
{
cout << "C " << p[j] << endl;
return 0;
}
}
}
}
}
cout << "C 1" << endl;
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #686 (Div. 3) (0) | 2020.11.25 |
|---|---|
| Codeforces Round #685 (Div. 2) (3) | 2020.11.23 |
| Codeforces Round #669 (Div. 2) (0) | 2020.09.09 |
| Codeforces Round #668 (Div. 1, Div. 2) (0) | 2020.09.07 |
| Codeforces Round #666 (Div. 1, Div.2) + 후기 (5) | 2020.08.31 |