A - Divisibility Problem
Problem - A - Codeforces
codeforces.com
두 양의 정수 \(a\)와 \(b\)가 주어진다.
\(a\)에 1을 더하는 연산을 최소화해서 \(a\)가 \(b\)로 나눠 떨어지게 해야 한다.
만약 이미 \(a\)가 \(b\)로 나눠 떨어진다면, 답은 0이다.
그렇지 않다면, 1을 더하는 연산을 \(b-(a\%b)\)번 하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#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 main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll a, b; cin >> a >> b;
cout << (b - (a % b)) % b << '\n';
}
}
|
B - K-th Beautiful String
Problem - B - Codeforces
codeforces.com
\(n-2\)개의 'a'와 2개의 'b'로 이루어진 길이 \(n\)인 문자열들이 있다.
이 문자열들을 사전 순으로 정렬 했을 때, \(k\)번째 문자열을 출력해야 한다.
'b'가 문자열의 뒤쪽에 위치할수록 사전순으로 앞섬을 이용하면 2개의 b가 있어야 할 위치를 계산할 수 있다.
밑은 \(O(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
|
#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 main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n, k; cin >> n >> k;
ll ck = 0;
for (int i = 0; i < n - 1; i++)
{
if (ck + i + 1 >= k)
{
for (int j = 0; j < n; j++)
{
if (j == n - 2 - i) cout << 'b';
else if (j == n - (k - ck)) cout << 'b';
else cout << 'a';
}
cout << '\n';
break;
}
ck += i + 1;
}
}
}
|
C - Ternary XOR
Problem - C - Codeforces
codeforces.com
길이 \(n\)의 3진수가 주어진다.
두개의 \(n\)자리 3진수 \(a\)와 \(b\) 에 대해서 XOR 연산 ⊙를 다음과 같이 정의하자.
\(n\)자리 3진수 \(c\)가 \(c=a\)⊙\(b\) 를 만족한다면, \(c_i=(a_i+b_i)\%3\)
3진수 \(x\)가 주어졌을 때, \(a\)⊙\(b=x\)를 만족하면서 \(max(a,b)\)를 최소화 하는 두 3진수 \(a\)와 \(b\)를 찾아야 한다.
당연하게도, \(max(a,b)\)가 최소화 되려면 \(a+b=x\)가 되어야 하고 이때 \(|a-b|\)를 최소화하면 된다.
\(x\)의 맨 앞자리부터 검사해보자.
\(x_i\)가 0이면 \(a_i\)와 \(b_i\) 모두 0이면 된다.
\(x_i\)가 2면 \(a_i\)와 \(b_i\) 모두 1이면 된다.
\(x_i\)가 1이면 \(a_i\)는 1, \(b_i\)는 0이 되어야 한다.
\(a\)가 이미 더 큰 수가 되었기 때문에, 나머지 자릿수를 전부 0으로 채우고, \(b\)에 남은 \(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
|
#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 main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
string s; cin >> s;
string ans1, ans2;
bool bigger = false;
for (auto c : s)
{
if (bigger) ans1 += '0', ans2 += c;
else
{
if (c == '0') ans1 += '0', ans2 += '0';
else if (c == '2') ans1 += '1', ans2 += '1';
else
{
bigger = true;
ans1 += '1';
ans2 += '0';
}
}
}
cout << ans1 << '\n' << ans2 << '\n';
}
}
r
|
D - Carousel
Problem - D - Codeforces
codeforces.com
\(n\)마리의 동물이 그려져있는 회전 목마가 있다.
동물 그림은 \(1\)부터 \(n\)까지 번호가 매겨져있고, \(n\)번 그림 다음에는 다시 \(1\)번 그림이 온다.
이 회전목마를 색칠하려고 하는데, 서로 다른 두 동물이 연속되어 있으면서 같은 색깔로 칠해져 있지 않아야 한다.
이 조건을 만족하면서 가장 적은 색으로 회전목마를 색칠해야 한다.
케이스를 나눠서 생각해보자.
회전목마 전체에 같은 동물이 그려져 있다면, 1가지 색이면 충분하다.
\(n\)이 짝수라면, 2가지 색으로 칠할 수 있다.
연속되어 있는 모든 칸이 서로 다른 색깔을 가질 수 있기 때문이다. (1, 2, 1, 2, .... , 1, 2)
\(n\)이 홀수일 때가 문제인데, 연속되어 있는 같은 두 동물그림이 존재하면 두 칸을 모아 한 칸처럼 생각하고 \(n\)이 짝수일 때와 같이 처리하면 된다.
연속되어 있는 같은 두 동물그림이 존재하지 않는다면, 3가지 색이 필요하다.
|
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
|
#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 t[200001];
vector <int> stk;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int q; cin >> q;
while (q--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> t[i];
stk.clear();
stk.push_back(t[0]);
bool hasDouble = false;
for (int i = 1; i < n; i++)
{
if (t[i] != stk.back()) stk.push_back(t[i]);
else hasDouble = true;
}
if (stk.size() > 1 && stk.front() == stk.back())
hasDouble = true;
if (stk.size() == 1)
{
cout << "1\n";
for (int i = 0; i < n; i++) cout << "1 ";
cout << '\n';
continue;
}
else
{
if (n % 2 == 0)
{
cout << "2\n";
for (int i = 0; i < n; i++) cout << i % 2 + 1 << ' ';
cout << '\n';
}
else
{
if (hasDouble)
{
cout << "2\n";
int flag = 0;
for (int i = 0; i < n; i++)
{
if (!flag && i && t[i - 1] == t[i]) flag = 1;
cout << (i + flag) % 2 + 1 << ' ';
}
cout << '\n';
}
else
{
cout << "3\n";
for (int i = 0; i < n - 1; i++) cout << i % 2 + 1 << ' ';
cout << "3\n";
}
}
}
}
}
|
E - Tree Queries
Problem - E - Codeforces
codeforces.com
\(n\)개 정점을 가진 트리가 주어지고, \(m\)개의 쿼리가 주어진다.
각 쿼리는 \(k_i\)개의 서로 다른 정점으로 이루어져 있는데, 루트에서 시작하는 모든 경로 중 이 모든 정점을 포함하거나 거리가 1인 경로가 존재하는지 알아내야 한다.
임의의 트리에서 루트에서 리프까지 경로를 하나 그린 다음, 거리가 1인 정점이 가지고 있는 특징을 관찰해 보면 해당하는 정점의 부모는 그 경로에 포함된 정점 중 하나라는 사실을 알 수 있다.
따라서 주어진 \(k_i\)개의 정점의 부모가 한 경로에 모두 포함될 수 있는지 알아내면 되는데,
정점(의 부모)들을 레벨별로 정렬 한 후, 연속된 모든 두 정점 \(x, y\)에 대해 \(LCA(x, y)\)가 \(x\)또는 \(y\)인지 확인하면 된다.
|
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
|
#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 <int> graph[200001];
int par[200001][20];
int lv[200001];
void DFS(int v, int p, int l)
{
par[v][0] = p;
lv[v] = l;
for (auto nv : graph[v])
{
if (nv == p) continue;
DFS(nv, v, l + 1);
}
}
bool comp(int a, int b) { return lv[a] < lv[b]; }
int lca(int v1, int v2)
{
for (int i = 19; i >= 0; i--)
{
if (lv[par[v2][i]] >= lv[v1]) v2 = par[v2][i];
}
return v2;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n - 1; i++)
{
int a, b; cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
DFS(1, 1, 0);
for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++)
par[i][j] = par[par[i][j - 1]][j - 1];
while (m--)
{
vector <int> v;
int k; cin >> k;
while (k--)
{
int x; cin >> x;
x = par[x][0];
v.push_back(x);
}
sort(v.begin(), v.end(), comp);
v.erase(unique(v.begin(), v.end()), v.end());
bool ans = true;
for (int i = 1; i < v.size(); i++)
{
int pv = v[i - 1];
int cv = v[i];
int par = lca(pv, cv);
if (par != pv)
{
ans = false;
break;
}
}
if (ans) cout << "YES\n";
else cout << "NO\n";
}
}
|
F - Make k Equal
Problem - F - Codeforces
codeforces.com
원소가 \(n\)개인 배열 \(a\)가 주어지고, 정수 \(k(\le n)\)가 주어진다.
이 배열에서 다음과 같은 연산을 할 수 있다.
1. 가장 작은 원소중 하나를 골라 1을 더한다.
2. 가장 큰 원소중 하나를 골라 1을 뺀다.
이 때 최소 \(k\)개의 원소가 같게 하기 위한 최소 연산 횟수를 알아내야 한다.
먼저 배열을 정렬한 후, 각각의 원소 \(a_i\)를 \(k\)개 만들기 위한 연산 수를 계산해보자.
\(a_i\)가 이미 \(k\)개 이상이라면, 필요한 연산은 0회이다.
그렇지 않다면, \(a_i\)보다 작은 원소에 1을 더해 \(a_i\)로 만들거나 \(a_i\)보다 큰 원소에 1을 빼서 \(a_i\)로 만들어야 한다.
1번 연산만을 이용해 문제를 푼다고 생각해보자.
어떤 원소에 '가장 작은 원소에 1을 더하는 연산'을 한 후 결과가 \(a_i\)가 되려면 가장 작은 원소가 \(a_i-1\)이어야 하는데, 결국 \(a_i\)보다 작은 모든 원소를 일단 \(a_i-1\)로 만들어야 한다는 것을 의미한다.
\(a_i\)보다 작은 원소의 개수는 배열 \(a\)를 정렬해두었기 때문에 이분탐색으로 구할 수 있다. 이 값을 \(lcnt\)라고 하자.
\(a_i\)보다 작은 모든 원소의 합은 부분합을 미리 계산해 둠으로써 \(O(1)\)에 구할 수 있다. 이 값을 \(lsum\)이라고 하자.
\(a_i\)보다 작은 원소를 \(a_i-1\)로 만드는데 필요한 연산수는 \(lcnt\cdot(a_i-1) - lsum\)이다.
2번 연산도 같은 방법으로 계산 할 수 있고,
1번 연산만을 이용하는 경우
2번 연산만을 이용하는 경우
1번과 2번 연산을 모두 이용하는 경우
3가지를 각각 계산해 연산 횟수의 최소값을 구하면 된다.
|
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
|
#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; }
ll k, n;
ll a[200001];
ll psum[200001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + a[i];
ll ans = 2e18;
for (int i = 1; i <= n; i++)
{
ll l = lower_bound(a + 1, a + n + 1, a[i]) - a;
ll r = upper_bound(a + 1, a + n + 1, a[i]) - a;
if (r - l >= k)
{
ans = 0;
break;
}
ll rm = k - (r - l);
ll lcnt = l - 1;
ll rcnt = n + 1 - r;
ll lsum = (a[i]-1) * lcnt - (psum[l - 1]);
ll rsum = (psum[n] - psum[r - 1]) - (a[i] + 1) * rcnt;
if (lcnt >= rm)
{
ll res = lsum + rm;
ans = min(ans, res);
}
if (rcnt >= rm)
{
ll res = rsum + rm;
ans = min(ans, res);
}
ll res = lsum + rsum + rm;
ans = min(ans, res);
}
cout << ans;
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #633 (Div. 1, Div. 2) (0) | 2020.04.13 |
|---|---|
| Educational Codeforces Round 85 (0) | 2020.04.12 |
| Codeforces Round #632 (Div. 2) (2) | 2020.04.09 |
| Codeforces Round #631 (Div. 1, Div. 2) (0) | 2020.04.07 |
| Codeforces Round #630 (Div. 2) (2) | 2020.04.06 |